首页 / 面试 / 剑指offer:面试题18、树的子结构
剑指offer:面试题18、树的子结构
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了剑指offer:面试题18、树的子结构,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1272字,纯文字阅读大概需要2分钟。
内容图文
![剑指offer:面试题18、树的子结构](/upload/InfoBanner/zyjiaocheng/1242/af4fcbea98ea46348636e40e5e381d11.jpg)
题目描述
输入两棵二叉树A,B,判断B是不是A的子结构。(ps:我们约定空树不是任意一个树的子结构)
代码示例
public class Offer18 {
public static void main(String[] args) {
//构建树1
TreeNode root1 = new TreeNode(1);
root1.left = new TreeNode(2);
root1.right = new TreeNode(3);
root1.left.left = new TreeNode(4);
root1.left.right = new TreeNode(5);
//构建树2
TreeNode root2 = new TreeNode(1);
root2.left = new TreeNode(2);
root2.right = new TreeNode(3);
//for test
Offer18 testObj = new Offer18();
System.out.println(testObj.hasSubTree(root1, root2));
}
static class TreeNode {
int val;
TreeNode left = null;
TreeNode right = null;
TreeNode(int val) {
this.val = val;
}
}
public boolean hasSubTree(TreeNode root1, TreeNode root2) {
if (root1 == null || root2 == null) {
return false;
}
return isSubtreeFromRoot(root1,root2) || hasSubTree(root1.left, root2) || hasSubTree(root1.right, root2);
}
//从根节点依次向下比较
private boolean isSubtreeFromRoot(TreeNode root1, TreeNode root2) {
if (root2 == null)
return true;//已经递归到root2没有节点了
if (root1 == null)
return false;//root2不为null而root1为null所以返回false
if (root1.val != root2.val)
return false;
//递归判定左右节点是否都满足要求
return isSubtreeFromRoot(root1.left, root2.left)
&& isSubtreeFromRoot(root1.right, root2.right);
}
}
原文:https://www.cnblogs.com/ITxiaolei/p/13166990.html
内容总结
以上是互联网集市为您收集整理的剑指offer:面试题18、树的子结构全部内容,希望文章能够帮你解决剑指offer:面试题18、树的子结构所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。