LeetCode 889 Construct Binary Tree from Preorder and Postorder Traversal

    
        标签：
        
            二叉树
        
            LeetCode
        
    发布于：2022-02-06 21:50:36
    编辑于：2022-02-06 22:20:37
    浏览量：655

概述

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

为什么题目说答案可能不唯一呢？

我们假设前序遍历的第二个元素是左子树的根节点，但实际上左子树可能是空指针，这个元素可能是右子树的根节点。

那为什么之前使用别的组合时（前序中序，中序后续）不用关心该假设是否成立呢？因为那两种情况下我们仅依赖了根元素的值来求出左右子树的 size，其实并没有依赖该假设。

迭代法

class Solution {
public:
    vector<int>* preorder;
    map<int, int> postmap;
    TreeNode* constructFromPrePost(vector<int>& preorder, vector<int>& postorder) {
        this->preorder = &preorder;
        for (int i = 0; i < postorder.size(); i ++) {
            postmap[postorder[i]] = i;
        }
        return helper(0, preorder.size() - 1, 0 , postorder.size() - 1);
    }
    
    TreeNode* helper(int i, int j, int m, int n) {
        if (i > j) return nullptr;
        auto root = new TreeNode((*preorder)[i]);
        if (i + 1 > j) return root;  // !
        int leftValue = (*preorder)[i + 1];
        int leftPostIdx = postmap[leftValue];
        int rightSize = n - leftPostIdx - 1;
        
        root->left = helper(i + 1, j - rightSize, m, n - rightSize - 1);
        root->right = helper(j - rightSize + 1, j, n - rightSize, n - 1);
        return root;
    }
};

Links: leetcode-889-construct-binary-tree-from-preorder-and-postorder-traversal