剑指 Offer 26. 树的子结构

, 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (A == null || B == null) {
            return false;
        }

        return treeContains(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B); // 注意 DFS 调用的是当前方法
    }

    private boolean treeContains(TreeNode rootA, TreeNode rootB) {
        if (rootB == null) {
            // B 树已经遍历完成，确认 A 树包含 B 树
            return true;
        }
        if (rootA == null) {
            return false;
        }
        
        return rootA.val == rootB.val && treeContains(rootA.left, rootB.left) && treeContains(rootA.right, rootB.right);
    }
}

注意此题要求 A 树包含 B 树，而不是子树相等，注意与 572. Subtree of Another Tree 的区别。

References

剑指 Offer 26. 树的子结构