StarWalker

Where my heart will take me

0%

Leetcode100-Same Tree

Posted on Edited on In Views: Valine:
Solution Report of LeetCode Accepted

Description

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

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

Solution

Solution 1: Recursion

Time Complex:

Space Complex: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * 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;
        if (p.val != q.val) return false;
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}

Solution 2: Iteration

Time Complex:

Space Complex: 

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
// Iteration solution, use stack to preorder trees
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        Stack<TreeNode> stP = new Stack<>();
        Stack<TreeNode> stQ = new Stack<>();
        if (p != null){
            stP.push(p);
        }
        if (q != null){
            stQ.push(q);
        }
        
        while(!stP.isEmpty() && !stQ.isEmpty()){
            TreeNode nodeP = stP.pop();
            TreeNode nodeQ = stQ.pop();
            if (nodeP.val != nodeQ.val){
                return false;
            }
            if (nodeP.left != null){
                stP.push(nodeP.left);
            }
            if (nodeQ.left != null){
                stQ.push(nodeQ.left);
            }
            if (stP.size() != stQ.size()){
                return false;
            }
            if (nodeP.right != null){
                stP.push(nodeP.right);
            }
            if (nodeQ.right != null){
                stQ.push(nodeQ.right);
            }
            if (stP.size() != stQ.size()){
                return false;
            }            
        }
        return stP.size() == 0 && stQ.size() == 0;
    }
}