黑马程序员技术交流社区

标题: 【上海校区】算法题（三十八）：判断树的子结构 [打印本页]

---

作者: 梦缠绕的时候    时间: 2018-11-26 09:12
标题: 【上海校区】算法题（三十八）：判断树的子结构
题目描述
输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

分析
从A树根结点开始遍历，如果结点与B树结点相等，则递归判断左子结点和右子结点的情况；若不等，则往下遍历A树左右结点各自与B树的情况。

已AC

代码
public class ChildTree {

        public static boolean HasSubtree(TreeNode root1, TreeNode root2){
                if (root1 == null || root2 == null) return false;
                return fun(root1, root2) || HasSubtree(root1.left, root2)||HasSubtree(root1.right, root2);
        }
       
        public static boolean fun(TreeNode root1, TreeNode root2){
                if(root1 == null){
                        return root2==null;
                }
                if(root2 == null){
                        return true;
                }
                if(root1.val == root2.val){
                        return fun(root1.left, root2.left) && fun(root1.right, root2.right);
                }
                return false;
        }
}

---------------------
作者：另一个我竟然存在
来源：CSDN
原文：https://blog.csdn.net/qq_24034545/article/details/84378708
版权声明：本文为博主原创文章，转载请附上博文链接！

---

作者: 不二晨    时间: 2018-11-28 15:48
奈斯

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2