[LeetCode] Problem 100 - Same Tree

Posted on | In ,

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

No.1

Input:

1
2
3
4
5
   1         1
  / \       / \
 2   3     2   3

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

Output: true

No.2

Input:

1
2
3
4
5
   1         1
  /           \
 2             2

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

Output: false

No.3

Input:

1
2
3
4
5
   1         1
  / \       / \
 2   1     1   2

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

Output: false

Code

1
2
3
4
5
6
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
1
2
3
4
5
6
7
8
public boolean isSameTree(TreeNode p, TreeNode q) {
    if (p == null && q == null)
        return true;
    else if (p == null || q == null || p.val != q.val)
        return false;
    
    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}