树的子结构

题目描述

输入两棵二叉树A,B,判断B是不是A的子结构。(ps:我们约定空树不是任意一个树的子结构)

思路

1.递归比较两个数的结构。
2.比较A树和B树当前的结点,若A树和B树的值相等,则继续比较它们的左右子树;若不相等,则拿A树的左子树和右子树进行同样的过程。
3.当B树遍历到了空结点,说明B是A的子结构;否则不是A的子结构。

Java代码实现

 public boolean HasSubtree(TreeNode root1,TreeNode root2) {
 if(root1 == null || root2 == null){
 return false;
 }
 boolean flag = judge(root1,root2);
 if(!flag){
 flag = HasSubtree(root1.left,root2);
 }
 if(!flag){
 flag = HasSubtree(root1.right,root2);
 }
 return flag;
 }
 private boolean judge(TreeNode root1,TreeNode root2){
 if(root2 == null)
 return true;
 if(root1 == null)
 return false;
 if(root1.val != root2.val)
 return false;
 return judge(root1.left,root2.left)&&judge(root1.right,root2.right);
 }

Golang代码实现

func HasSubtree(s *TreeNode, t *TreeNode) bool {
 if s == nil || t == nil{
 return false
 }
 flag := judgeTree(s,t)
 if !flag{
 flag = HasSubtree(s.Left,t)
 }
 if !flag{
 flag = HasSubtree(s.Right,t)
 }
 return flag
}
func judge(s *TreeNode, t *TreeNode) bool {
 if t == nil{
 return true
 }
 if s == nil && t != nil{
 return false
 }
 if s != nil && t == nil{
 return false
 }
 
 if s.Val != t.Val {
 return false
 }
 return judge(s.Left,t.Left) && judge(s.Right,t.Right)
}

本文来自:简书

感谢作者:youzhihua

查看原文:树的子结构

• 编辑
• 预览