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)$