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分别两颗树的高度

94 Binary Tree Inorder Traversal

114 Flatten Binary Tree to Linked List

Last modified 2yr ago

Copy link

Contents

100. Same Tree

1. Question

2. Implementation

3. Time & Space Complexity