572. Subtree of Another Tree

, 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (root == null) {
            return false;
        }

        return treeEquals(root, subRoot) || isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot); // 注意 DFS 调用的是当前方法
    }

    private boolean treeEquals(TreeNode rootA, TreeNode rootB) {
        if (rootA != null && rootB != null) {
            return rootA.val == rootB.val && treeEquals(rootA.left, rootB.left) && treeEquals(rootA.right, rootB.right);
        } else {
            return rootA == null && rootB == null;
        }
    }
}

注意此题要求 A 树与 B 树完全相等而不是 A 树包含 B 树。

References

572. Subtree of Another Tree