LeetCode572-另一个树的子树

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/subtree-of-another-tree/

中文链接：https://leetcode-cn.com/problems/subtree-of-another-tree/

题目详述

给定两个非空二叉树 s 和 t，检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。

示例 1:
给定的树 s:

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

给定的树 t：

1
2
3
  4 
 / \
1   2

返回 true，因为 t 与 s 的一个子树拥有相同的结构和节点值。

示例 2:
给定的树 s：

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

给定的树 t：

1
2
3
  4
 / \
1   2

返回 false。

题目详解

  • 写一个判断是否是相同的树的方法，来判断两棵树是否相同。
  • 判断这棵树是否是当前结点作为根结点的树的子树的逻辑：对于每一个结点，判断当前结点作为根结点的树和这棵树是否是相同的树。若是，则直接返回 true，否则递归判断这棵树是否是它的左孩子作为根结点和右孩子作为根结点的树的子树。
1
2
3
4
5
6
7
8
9
10
11
12
13
public class LeetCode_00572 {

    public boolean isSubtree(TreeNode s, TreeNode t) {
        if (s == null) return false;
        return isSame(s, t) || (isSubtree(s.left, t) || isSubtree(s.right, t));
    }

    private boolean isSame(TreeNode s, TreeNode t) {
        if (s == null && t == null) return true;
        if (s == null || t == null) return false;
        return s.val == t.val && isSame(s.left, t.left) && isSame(s.right, t.right);
    }
}