题解 | #牛群的树形结构重建#

牛群的树形结构重建

https://www.nowcoder.com/practice/bcabc826e1664316b42797aff48e5153

知识点

树,递归

解题思路

这个问题可以使用递归来解决。我们可以根据中序遍历和后序遍历的特点来重建二叉树。

在后序遍历中,最后一个元素是根节点。然后,在中序遍历中,根节点的位置将数组分成了左子树和右子树两部分。

我们可以从后序遍历中取出根节点,然后在中序遍历中找到根节点的位置。根节点左边的元素构成了左子树的中序遍历,根节点右边的元素构成了右子树的中序遍历。

然后,我们可以递归地建立左子树和右子树,分别使用左子树的中序遍历和后序遍历构建左子树,使用右子树的中序遍历和后序遍历构建右子树。

最后,我们将根节点连接到左子树和右子树上,构建整棵树。

Java题解

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     *
     * @param inOrder int整型一维数组
     * @param postOrder int整型一维数组
     * @return TreeNode类
     */
    public TreeNode buildTree(int[] inOrder, int[] postOrder) {
        if (inOrder == null || postOrder == null ||
                inOrder.length != postOrder.length) {
            return null;
        }

        // 构建二叉树
        return buildTreeRecursive(inOrder, postOrder, 0, inOrder.length - 1, 0,
                                  postOrder.length - 1);
    }

    private TreeNode buildTreeRecursive(int[] inOrder, int[] postOrder, int inStart,
                                        int inEnd, int postStart, int postEnd) {
        if (inStart > inEnd || postStart > postEnd) {
            return null;
        }

        // 创建根节点
        TreeNode root = new TreeNode(postOrder[postEnd]);

        // 在中序遍历中找到根节点的位置
        int rootIndex = inStart;
        while (rootIndex <= inEnd && inOrder[rootIndex] != root.val) {
            rootIndex++;
        }

        // 构建左子树
        int leftTreeSize = rootIndex - inStart;
        root.left = buildTreeRecursive(inOrder, postOrder, inStart, rootIndex - 1,
                                       postStart, postStart + leftTreeSize - 1);

        // 构建右子树
        root.right = buildTreeRecursive(inOrder, postOrder, rootIndex + 1, inEnd,
                                        postStart + leftTreeSize, postEnd - 1);

        return root;
    }
}

全部评论

相关推荐

不愿透露姓名的神秘牛友
昨天 15:58
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-09 16:15
我应届生,去年10月份开始在这家公司实习,到今年10月份正好一年想(实习+试用期),在想要不要提前9月份就离职,这样好找工作些,但又差一个月满一年,又怕10月份国庆回来离职,容易错过了下半年的金九银十,到年底容易gap到年后
小破站_程序员YT:说这家公司不好吧,你干了快一年 说这家公司好吧,你刚毕业就想跑路说你不懂行情吧,你怕错过金九银十说 你懂行情吧,校招阶段在实习,毕业社招想换工作 哥们,我该怎么劝你留下来呢
应届生,你找到工作了吗
点赞 评论 收藏
分享
06-15 02:05
已编辑
南昌航空大学 数据分析师
Eason三木:你如果想干技术岗,那几个发公众号合唱比赛的经历就去掉,优秀团员去掉,求职没用。然后CET4这种不是奖项,是技能,放到下面的专业技能里或者单独列一个英语能力。 另外好好改改你的排版,首行缩进完全没有必要,行间距好好调调,别让字和标题背景黏在一起,你下面说能做高质量PPT你得展现出来啊,你这简历排版我用PPT做的都能比你做的好。 然后自我评价,你如果要干数据工程师,抗压能力强最起码得有吧。
简历中的项目经历要怎么写
点赞 评论 收藏
分享
来个大佬救一下,为上投了都是石沉大海了,没实习经历的话怕秋招直接进不了面。什么实习这么难找,基本
心态爆炸了:现在正式的岗位都少,实习基本不咋招的,除了大厂,中小企业其实没那么多岗位需求,就算是有,大多都是招一两个廉价劳动力,同时,他们也会希望你一来就能干活的,没时间培训你,就让你了解公司的项目,你了解完就可以开始干活。再者是,很多低质量的实习其实用处没有那么大的。我去年也是找实习找到破防,最后去了一家深圳的小公司实习,工作对我来说很简单,甚至不如我在学校做的项目,秋招的时候,这段实习经历也并没有帮上什么忙,投递简历,依旧非常低的回复率。低回复率是常态,尤其是找实习,找不到,那就把重心放在优化自己的简历和项目,多看八股文,锻炼自己的面试能力,多看别人的面经,自己模拟面试,等秋招的时候,只要有那么寥寥几次,好好抓住那几次机会。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务