Reference: LeetCode
Difficulty: Easy

Problem

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 1
Input: 1 1
/ \ / \
2 3 2 3

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

Output: true

// 2
Input: 1 1
/ \
2 2

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

Output: false

Analysis

Recursion

Note: Do the null check at the beginning.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public boolean isSameTree(TreeNode p, TreeNode q) {
return preorder(p, q);
}

private boolean preorder(TreeNode p, TreeNode q) {
if (p == null || q == null) {
return p == null && q == null;
}
if (p.val != q.val) return false;
return preorder(p.left, q.left) && preorder(p.right, q.right);
// if (preorder(p.left, q.left) == false) return false;
// if (preorder(p.right, q.right) == false) return false;
// return true;
}

Time: $O(N)$
Space: $O(h)$

Iteration

Use two stacks to simulate the preorder traversal.

Note:

  • Stack and Queue can contain null elements, while Deque can’t.
  • Do null check first, and then do the value check. Make sure p and q are not null.
  • The while condition should consider two stacks at the same time.
  • The return statement should check if two stacks are empty at the same time.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public boolean isSameTree(TreeNode p, TreeNode q) {
Stack<TreeNode> pStack = new Stack<>();
Stack<TreeNode> qStack = new Stack<>();
pStack.push(p); qStack.push(q);

while (pStack.size() > 0 && qStack.size() > 0) {
p = pStack.pop();
q = qStack.pop();

// null check
if (p == null || q == null) {
if (p == null && q == null) continue;
else return false;
}

// value check
if (p.val != q.val) return false;

// push to stack
pStack.push(p.right); // could be null, but no worry.
qStack.push(q.right);
pStack.push(p.left);
qStack.push(q.left);
}

return pStack.size() == 0 && qStack.size() == 0;
}

Time: $O(N)$
Space: $O(h)$


Comment