首页 > 代码库 > 树的子结构
树的子结构
题目:输入两棵二叉树A,B,判断B是不是A的子结构。(ps:我们约定空树不是任意一个树的子结构)
思路:关于树的题目基本都需要用到递归(因为树就是递归定义的。。。。。),见代码注释
/** public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */ public boolean HasSubtree(TreeNode root1,TreeNode root2) { if(root2==null) return false; //当Tree1和Tree2都不为零的时候,才进行比较。否则直接返回false if(root1==null && root2!=null) return false; boolean flag = false; if(root1.val==root2.val){ //如果找到了对应Tree2的根节点的点 //以这个根节点为为起点判断是否包含Tree2 flag = isSubTree(root1,root2); } //如果找不到,那么就再去root的左儿子当作起点,去判断时候包含Tree2 if(!flag){ flag = HasSubtree(root1.left, root2); } //如果还找不到,那么就再去root的右儿子当作起点,去判断时候包含Tree2 if(!flag){ flag = HasSubtree(root1.right, root2); } return flag; } private boolean isSubTree(TreeNode root1, TreeNode root2) { //如果Tree2已经遍历完了都能对应的上,返回true if(root2==null) return true; //如果Tree2还没有遍历完,Tree1却遍历完了。返回false if(root1==null && root2!=null) return false; //如果根节点对应的上,那么就分别去子节点里面匹配 if(root1.val==root2.val){ return isSubTree(root1.left, root2.left) && isSubTree(root1.right, root2.right); }else{ return false; } }
树的子结构
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。