题目描述
输入两棵二叉树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)
}
有疑问加站长微信联系(非本文作者)