算法:树的子结构
树的子结构
树的子结构
输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
分析
通过递归进行判断: 如果A当前节点等于B的根节点, 递归判断是否是子树
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| public class Solution {
public boolean HasSubtree(TreeNode root1, TreeNode root2) {
if (root2 == null || root1 == null) return false;
return helper(root1, root2) || HasSubtree(root1.left, root2) || HasSubtree(root1.right, root2);
}
private boolean helper(TreeNode root1, TreeNode root2) {
if (root2 == null) return true;
if (root1 == null) return false;
if (root1.val == root2.val) return helper(root1.left, root2.left) && helper(root1.right, root2.right);
return false;
}
}
|
