[LeetCode] 100. Same Tree

Posted on | In

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:

1
2
3
4
5
6
7
Input:     1         1
          / \       / \
         2   3     2   3

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

Output: true

Example 2:

1
2
3
4
5
6
7
Input:     1         1
          /           \
         2             2

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

Output: false

Example 3:

1
2
3
4
5
6
7
Input:     1         1
          / \       / \
         2   1     1   2

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

Output: false

Explanation 1

  1. We can use recursion method to solve this problem. If two tree are the same, then their root.val are the same, and root.left.val are the same, and root.right.val are the same.

  2. The base case is if two trees are NULL, then they are the same, else if one tree is NULL another is not NULL, then we return false.

Solution 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) return true;
        if (p == null || q == null) return false;
        return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}

Explanation 2

  1. We can also use BFS (level-order traversal) to solve this problem. The difference is we can’t pop the nodes from both queue and compare them because in the problem’s Example 2, the second level have the same values 2, but one of them is belongs to the left child, and another one belongs to the right child. So before we push the node into the queue, we need to compare both current nodes’ left childs and right childs.

  2. First, we make a helper function to compare 2 root nodes if they both are NULL or they both have the same value, then return true, else return false.

  3. Initialize two queues q1 to hold the TreeNodes for Tree p, q2 to hold the TreeNodes for Tree q. Then, we push root node p to q1 and push root node q to q2.

  4. While both queue are not empty, we poll out the nodes curP and curQ from both queues. Then we pass their left childs to the helper function, and pass their right childs to the helper function to compare curP.left is the same as curQ.left, and curP.right is the same as curQ.right. If one of the helper function return false, we immediately return false. Else, we push their left child and right child to the queue. Repeat until one of the queue is empty.

  5. Outside the while loop, we can return true.

Solution 2

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    boolean helper(TreeNode p, TreeNode q) {
        if (p == null && q == null) return true;
        if (p == null || q == null) return false;
        if (p.val != q.val) return false;
        return true;
    }

    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (!helper(p, q)) return false;
        Queue<TreeNode> q1 = new LinkedList<>();
        Queue<TreeNode> q2 = new LinkedList<>();
        if (p != null) q1.offer(p);
        if (q != null) q2.offer(q);
        while(!q1.isEmpty() && !q2.isEmpty()) {
            TreeNode curP = q1.poll();
            TreeNode curQ = q2.poll();
            if (!helper(curP.left, curQ.left) || !helper(curP.right, curQ.right)) return false;
            if (curP.left != null) q1.offer(curP.left);
            if (curP.right != null) q1.offer(curP.right);
            if (curQ.left != null) q2.offer(curQ.left);
            if (curQ.right != null) q2.offer(curQ.right);
        }
        return q1.isEmpty() && q2.isEmpty();
    }
}