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:
1
Input:
2
1 1
3
/ \ / \
4
2 3 2 3
5
6
[1,2,3], [1,2,3]
7
8
Output: true
Copied!
Example 2:
1
Input:
2
1 1
3
/ \
4
2 2
5
6
[1,2], [1,null,2]
7
8
9
Output: false
Copied!
Example 3:
1
Input:
2
1 1
3
/ \ / \
4
2 1 1 2
5
6
[1,2,1], [1,1,2]
7
8
9
Output: false
Copied!

2. Implementation

(1) Recursion
1
class Solution {
2
public boolean isSameTree(TreeNode p, TreeNode q) {
3
if (p == null && q == null) return true;
4
if (p == null || q == null || p.val != q.val) return false;
5
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
6
}
7
}
Copied!

3. Time & Space Complexity

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