LeetCode 106 Construct Binary Tree from Inorder and Postorder Traversal

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

概述

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;
    }
};

Links: leetcode-106-construct-binary-tree-from-inorder-and-postorder-traversal