输入两棵二叉树A,B,判断B是不是A的子结构。(ps:我们约定空树不是任意一个树的子结构)
二叉树结构:
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
注:点击左下角的阅读原文即可跳转到原文,可以提交代码
对于与二叉树有关的题目,90% 是采取递归的方式来解决比较简单的,这道题也是。
首先我们先以 A 的根节点 root1 作为起点来判断 B 是否为 A的子结构。 如果是则直接返回 true,如果不是,则递归以 root1.left 和 root1.right 作为起点来判断。代码如下:
public class 树的子结构 {
public boolean HasSubtree(TreeNode root1,TreeNode root2) {
if (root2 == null || root1 == null) {
return false;
}
// 判断 B 是否为 A 的子结构
return isSubTree(root1, root2);
}
// 判断 B 是否为 A 的子结构
private boolean isSubTree(TreeNode root1, TreeNode root2) {
if (root1 == null) {
return false;
}// 以root1为root2的根节点,判断子结构是否成立
if (judge(root1, root2)) {
return true;
} else {
// 如果root1作为起点不行,则递归判断左右节点
return isSubTree(root1.left, root2) || isSubTree(root1.right, root2);
}
}
// 以root1为root2的根节点,判断子结构是否成立
private boolean judge(TreeNode root1, TreeNode root2) {
if(root2 == null)
return true;
if(root1 == null)
return false;
if(root1.val == root2.val)
return judge(root1.left, root2.left) && judge(root1.right, root2.right);
return false;
}
}
学习更多算法 + 计算机基础知识,欢迎关注我的微信公众号,每天准时推送技术干货