树的子结构

Posted on Edited on In Views: Waline: Symbols count in article: 144 Reading time ≈ 1 mins.

题解方法

  • 递归

递归

  1. 递归判断 A 的当前节点是否包含 B。
  2. 分别递归遍历 A 的左右子树，过程中递归判断当前节点是否包含 B。

核心代码

递归

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

private boolean isContained(TreeNode A, TreeNode B) {
	// B 遍历结束，说明 B 是 A 的子结构
	if (B == null) {
		return true;
	}
	if (A == null) {
		return false;
	}
	if (A.val != B.val) {
		return false;
	}
	return isContained(A.left, B.left) && isContained(A.right, B.right);
}

题目来源