Leetcode/Bloomberg -- 100. Same Tree (Recursion)

100. Same Tree (Recursion)

• Difficulty: Easy

https://leetcode.com/problems/same-tree/

Given two binary trees, write a function to check if they are equal or not.

Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

思路：4 base conditions, recursively traverse tree, return true when both tree traverse to the end point
Complexity: O(N)

public class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        //4 cases to consider
        if(p==null&&q==null)return true;
        if(p==null&&q!=null)return false;//can be merged ||
        if(p!=null&&q==null)return false;
        if(p.val!=q.val)return false;
        return  isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
    }
}