[LeetCode] Problem 572 - Subtree of Another Tree

Posted on | In ,

Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A subtree of s is a tree consists of a node in s and all of this node’s descendants. The tree s could also be considered as a subtree of itself.

Example

No.1

Given tree s:

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

Given tree t:

1
2
3
  4 
 / \
1   2

Return true, because t has the same structure and node values with a subtree of s.

No.2

Given tree s:

1
2
3
4
5
6
7
    3
   / \
  4   5
 / \
1   2
   /
  0

Given tree t:

1
2
3
  4
 / \
1   2

Return 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
9
10
11
12
13
14
15
16
17
18
19
public boolean isSubtree(TreeNode s, TreeNode t) {
    if (s == null)
        return false;

    if (isSameTree(s, t))
        return true;

    return isSubtree(s.left, t) || isSubtree(s.right, t);
}

private boolean isSameTree(TreeNode s, TreeNode t) {
    if (s == null && t == null)
        return true;

    if (s == null || t == null || s.val != t.val)
        return false;

    return isSameTree(s.left, t.left) && isSameTree(s.right, t.right);
}