题解 | #牛群的树形结构重建# 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);
    }
};

全部评论

相关推荐

06-25 16:25
梧州学院 Java
愿汐_:项目介绍那么长,然而你做了啥就一句话?
点赞 评论 收藏
分享
07-07 12:47
门头沟学院 Java
码农索隆:竟然还真有卡体检报告的
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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