首页 > itarticle > [leetcode] problem 572 – subtree of another tree

[leetcode] problem 572 – subtree of another tree

admin 11月 13, 2020 0

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  {
    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);
}
微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能