三道题搞懂子树问题

代码模板

public boolean f(TreeNode p, TreeNode q) {
        if(p==null&&q==null)return true;
        if(p==null||q==null||p.val!=q.val)return false;
        //false的条件
        return f(p.left,q.left)&&f(p.right,q.right);
    }

相同的树（LeetCode100）

初级：遍历即可，模板题

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p==null&&q==null)return true;
        if(p==null||q==null||p.val!=q.val)return false;
        return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
    }
}

对称的树（LeetCode101）

中级：把题目看成判断两棵子树是否符合条件即可

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root==null)  return true;
        return Symmetric(root.left,root.right);
    }
    public boolean Symmetric(TreeNode left,TreeNode right){
        if(left==null&&right==null) return true;
        if(left==null||right==null) return false;
        if(left.val!=right.val)  return false;
        return Symmetric(left.left,right.right)&&Symmetric(left.right,right.left);
    }
}

另一棵树的子树（LeetCode572）

高级：依旧是return的条件为比较的点

class Solution {
    public boolean isSame(TreeNode p,TreeNode q){
        if(p==null&&q==null)    return true;
        if(p==null||q==null||p.val!=q.val)    return false;
        return isSame(p.left,q.left)&&isSame(p.right,q.right);
    }
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if(root==null)  return false;
        return isSame(root,subRoot)||isSubtree(root.left,subRoot)||isSubtree(root.right,subRoot);
    }
}

通过这三道题想必你已经对子树问题有自己的见解了(⊙o⊙)~~