100 Same Tree

100. Same Tree

1. Question

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

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

Input:
     1         1
    / \       / \
   2   3     2   3

  [1,2,3],   [1,2,3]

Output: true

Example 2:

Input:
     1         1
    /           \
   2             2

   [1,2],     [1,null,2]


Output: false

Example 3:

Input:
     1         1
    / \       / \
   2   1     1   2

  [1,2,1],   [1,1,2]


Output: false

2. Implementation

(1) Recursion

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);
    }
}

3. Time & Space Complexity

Recursion: 时间复杂度: O(m + n), 空间复杂度O(h1 + h2), h1和h2分别两颗树的高度