原文链接: https://leetcode-cn.com/problems/check-subtree-lcci

英文原文

T1 and T2 are two very large binary trees. Create an algorithm to determine if T2 is a subtree of T1.

A tree T2 is a subtree of T1 if there exists a node n in T1 such that the subtree of n is identical to T2. That is, if you cut off the tree at node n, the two trees would be identical.

Note: This problem is slightly different from the original problem.

Example1:

 Input: t1 = [1, 2, 3], t2 = [2]
 Output: true

Example2:

 Input: t1 = [1, null, 2, 4], t2 = [3, 2]
 Output: false

Note:

1. The node numbers of both tree are in [0, 20000].

中文题目

检查子树。你有两棵非常大的二叉树：T1，有几万个节点；T2，有几万个节点。设计一个算法，判断 T2 是否为 T1 的子树。

如果 T1 有这么一个节点 n，其子树与 T2 一模一样，则 T2 为 T1 的子树，也就是说，从节点 n 处把树砍断，得到的树与 T2 完全相同。

注意：此题相对书上原题略有改动。

示例1:

 输入：t1 = [1, 2, 3], t2 = [2]
 输出：true

示例2:

 输入：t1 = [1, null, 2, 4], t2 = [3, 2]
 输出：false

提示：

1. 树的节点数目范围为[0, 20000]。

通过代码

高赞题解

思路
遍历t1的每个节点，判断以t1中的每个节点为根的子树是否与t2相同。详见代码：

private boolean isSame(TreeNode t1, TreeNode t2) {
    if (t1 == null && t2 == null) {
        return true;
    }

    if (t1 == null || t2 == null) {
        return false;
    }

    return t1.val == t2.val && isSame(t1.left, t2.left) && isSame(t1.right, t2.right);
}

public boolean checkSubTree(TreeNode t1, TreeNode t2) {
    if (t1 == null) {
        return t2 == null;
    }

    return isSame(t1, t2) || checkSubTree(t1.left, t2) || checkSubTree(t1.right, t2);
}

统计信息

通过次数	提交次数	AC比率
17159	23957	71.6%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言