LeetCode 106 Construct Binary Tree from Inorder and Postorder Traversal

标签: 二叉树 LeetCode 发布于:2022-02-06 21:31:16 编辑于:2022-02-06 21:49:55 浏览量:1105

概述

https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/

迭代法

看了好久才发现 i > j 写成 i < j 了,我佛了。

class Solution {
public:
    vector<int>* postorder;
    map<int, int> inmap;
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        this->postorder = &postorder;
        for (int i = 0; i < inorder.size(); i ++) {
            inmap[inorder[i]] = i;
        }
        return helper(0, inorder.size() - 1, 0, postorder.size() - 1);
    }
    
    TreeNode* helper(int i, int j, int m, int n) {
        if (i > j) return nullptr;
        int rootValue = (*postorder)[n];
        int rootInIndex = inmap[rootValue];
        int leftSize = rootInIndex - i;
        auto root = new TreeNode(rootValue);
        root->left = helper(i, i + leftSize - 1, m, m + leftSize - 1);
        root->right = helper(rootInIndex + 1, j, m + leftSize, n - 1);
        return root;
    }
};

未经允许,禁止转载,本文源站链接:https://iamazing.cn/