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.

同样还是对左右子树求递归，很多树的题目都可以用对子树递归来求解。需要注意的是，递归的空间复杂度就是递归的深度也就是树的深度。

public class Solution {
    //Time: O(n)  Space: O(depth of tree);
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        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);
    }
}