"Recursive processing of subproblems" -- judging whether two trees are the same tree -- and the subtree of another tree

“ Recursive processing of subproblems ”—— Look at the root node first , Look at the left and right subtrees

1. Check whether the two trees are the same

Question logic

1. Just take the root node Based on
   First judge The root node of the two trees Contrast
2. If two root nodes That's all right.
   Then look at Of this root node Left and right subtrees Is there a problem with the left and right subtrees of another root node
   

Original link

return false The situation of

1. Nothing is empty || The two values are different

return true

1. Both are empty

Recursion lies in return Recursive function

public boolean isSameTree(TreeNode p, TreeNode q) {
    
    // Here is just judgment   One is empty   A case that is not empty  .
    //  You have no judgment   Both are empty   and   Neither is empty 
    if(p == null && q != null || p != null && q == null) {
    
        return false;
    }

    if(p == null && q == null) {
    
        return true;
    }

    if(p.val != q.val) {
    
        return false;
    }

    //p != null && q != null && p.val == q.val
    return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
}

2. The subtree of another tree （ Time complexity ：O(n*m)）

Original link

    public boolean isSameTree(TreeNode p, TreeNode q) {
    
        // Here is just judgment   One is empty   A case that is not empty  .
        //  You have no judgment   Both are empty   and   Neither is empty 
        if(p == null && q != null || p != null && q == null) {
    
            return false;
        }

        if(p == null && q == null) {
    
            return true;
        }

        if(p.val != q.val) {
    
            return false;
        }

        //p != null && q != null && p.val == q.val
        return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
    }
    // Time complexity ：O(n*m)  hypothesis root The number of nodes in this tree n subRoot The number of nodes is m
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
    
        if(root == null) return false;

        if(isSameTree(root,subRoot)) return true;

        if(isSubtree(root.left,subRoot)) return true;

        if(isSubtree(root.right,subRoot)) return true;

        return false;
    }

Logic ：1. If the tree is empty There can be no subtree return flase

if(root == null) return false;

2. If root And subtree Is equal to the return true

if(isSameTree(root,subRoot)) return true;

3. If Left of root And Subtrees are exactly equal return true

if(isSubtree(root.left,subRoot)) return true;

4. If Right of root And Subtrees are exactly equal return true

if(isSubtree(root.right,subRoot)) return true;

5. if Not satisfied that return false

Be careful ： In fact, the code is During recursion , It's not just comparison Left and right of the root ,（ If there's nothing you want ） Also compare the left and right of the rest of the roots

reason ： The code is in the process of recursion , Walked through every root node