牛客_剑指offer题集——树的子结构（java实现）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了牛客_剑指offer题集——树的子结构（java实现），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1503字，纯文字阅读大概需要3分钟。

内容图文

题目链接：

https://www.nowcoder.com/practice/6e196c44c7004d15b1610b9afca8bd88?tpId=13&tqId=11170&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

思路：先通过层次遍历将a树中和b树根节点相同值的结点全部存入缓存数组，然后遍历缓存数组，通过判断二树结构是否相同的递归方法，来返回值

需要注意的点：在递归函数中，不能判断到A树的空值就返回，必须先改一下标记，否则很可能b树此处不为空而a树为空导致错误判断

代码实现：

package niuke;

public class 树的子结构 {
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        if(root1==null||root2==null) return false;
        /**
         * 使用层次遍历找出大一些的树中第二颗子树的根节点
         */
        TreeNode[] queue = new TreeNode[1000];
        int front = 0;
        int rear = 0;
        rear = (rear+1)%1000;
        TreeNode tn = root1;
        queue[rear] = tn;
        TreeNode[] buffer = new TreeNode[1000];
        int index = 0;
        while(front!=rear){
            front = (front+1)%1000;
            tn = queue[front];
            if(tn.val==root2.val){
                buffer[index] = tn;
                index++;
            }
            if(tn.left!=null) {
                rear = (rear + 1) % 1000;
                queue[rear] = tn.left;
            }
            if(tn.right!=null) {
                rear = (rear + 1) % 1000;
                queue[rear] = tn.right;
            }
        }
        boolean flag_in = false;
        for(TreeNode each :buffer){
            flag = true;
            if(each==null) break;
            inOrderTraversal(each,root2);
            if(flag){
                flag_in = true;
                break;
            }
        }
        return flag_in;
    }

    private boolean flag = true;

    private void inOrderTraversal(TreeNode root1,TreeNode root2){
        if(root2==null)return;
        if(root1==null||root1.val!=root2.val){
            flag = false;
            return;
        }
        inOrderTraversal( root1.left, root2.left);
        inOrderTraversal( root1.right, root2.right);
    }



}

代码已经ac

希望对大家有所帮助

以上

内容总结

以上是互联网集市为您收集整理的牛客_剑指offer题集——树的子结构（java实现）全部内容，希望文章能够帮你解决牛客_剑指offer题集——树的子结构（java实现）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端