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

牛群的树形结构重建

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

知识点

DFS 后序遍历 中序遍历

思路

后序遍历是顺序是“左右中”,中序遍历顺序是“左中右”。因此每次找到对应序列的后序遍历的最后一个数作为根节点,然后找到对应的左右子树的对应的范围,把问题化为原问题的子问题,用递归解决。

时间复杂度

最差情况是一条链,时间复杂度为O(n^2)

AC code(C++)

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param inOrder int整型vector 
     * @param postOrder int整型vector 
     * @return TreeNode类
     */
    TreeNode* buildTree(vector<int>& inOrder, vector<int>& postOrder) {
        int n = inOrder.size();
        function<TreeNode*(int, int, int, int)> dfs = [&](int l1, int r1, int l2, int r2) {
            auto val = postOrder[r2];
            auto root = new TreeNode(val);
            int len = 0;
            for (int i = l1; i <= r1 and inOrder[i] != val; i ++) {
                len ++;
            }
            if (len > 0) root->left = dfs(l1, l1 + len - 1, l2, l2 + len - 1);
            if (r1 - l1 - len > 0) root->right = dfs(l1 + len + 1, r1, l2 + len, r2 - 1);
            return root;
        };
        return dfs(0, n - 1, 0, n - 1);
    }
};

全部评论

相关推荐

机械打工仔:不管啥专业,找工作改简历的第一课先把你那排版改了,简历上不要写个人简历四个字,找你要简历的谁不知道这个是简历?而且还占那么多空间,直接把自己名字和基础信息写上面,整体字体大一些。 还有这种经典两页简历一页大空白,导出PDF的时候多了一页几乎全是白的你自己看着不难受吗随手的事为啥不能改掉呢,这是态度问题,你试想一下你是HR你打开简历看到格式都没调整过会是什么感受?你自己都不重视你的简历,HR更不会在意。 然后内容你那个做两年咖啡就别往里写了,简历在精不在多,你在往你的简历里打字的时候就要想好这东西对你要找的工作有没有帮助。自我评价写一行就行了,不如给专业技能单开一栏。核心课程均分90这个真别写了,把你上过的有用的专业课列出来也行。有很多地方废话很多的精炼一下,比如你校内项目第一个写的那些,全然没有重点。 好好修改一下,我看你内容也挺优秀的,别被一个随便做的简历耽误了,我一个同专业的打工人看了都揪心更别说一天看几百份简历的HR
听劝,我这个简历该怎么改...
点赞 评论 收藏
分享
绝迹的星:前端和后端写两份简历, 如果想干全栈就直接写求职意向为全栈工程师
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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