Poison

剑指 Offer 26. 树的子结构

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

// B is not null
if (A == null) {
return false;
}

return contains(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
}

private boolean contains(TreeNode A, TreeNode B) {
if (B == null) {
// 注意 B == null 即可返回 true, 无需 A == null, 因为是包含子树,即 A 及子节点可能都不为空,B 树只是 A 树的一部分
return true;
}

// B is not null
if (A == null || A.val != B.val) {
return false;
}

// A.val == B.val, continue to compare subtrees
return contains(A.left, B.left) && contains(A.right, B.right);
}
}
Reference

剑指 Offer 26. 树的子结构