【上海校区】算法题(三十八):判断树的子结构

python 未结 0 222
山西网络营销
山西网络营销 2021-07-22 15:20
悬赏:41
题目描述
输入两棵二叉树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
版权声明:本文为博主原创文章,转载请附上博文链接!

相关标签:
回答
  • 消灭零回复
提交回复