题解 | #树的子结构#
树的子结构
http://www.nowcoder.com/practice/6e196c44c7004d15b1610b9afca8bd88
class Solution {
public boolean HasSubtree(TreeNode root1,TreeNode root2) {
//这个函数是指当前root1的根与root2的根
//找到root1里的根节点与root2相同的值
if (root1==null||root2==null){
return false;
}
if (root1.val==root2.val&&(helper(root1.left,root2.left))&&(helper(root1.right,root2.right))){
//当前这个根就是相同的，看各自左右是否能对应
return true;
}else {
//如果不对应,换根
return HasSubtree(root1.left,root2)||HasSubtree(root1.right,root2);
}
}
public boolean helper(TreeNode root1,TreeNode root2){
//判断两个数是否是相同的
//注意！！！判断空的顺序非常重要
if (root2==null){
return true;
}
if (root1==null) {
return false;
}
if (root1.val==root2.val){
return helper(root1.left,root2.left)&&helper(root1.right,root2.right);
}else {
return false;
}
}
}先找A中的根与B根对应 然后在看对应的左右子树是否对应
在判断左右子树是否对应当中要注意 先判断b是否为空 如果b为空那么一定是子节点 因为上一层已经判断了根是相同了的
在helper中如果进来的节点值相同那么一次看左右对应的是不是相同的
