LeetCode 889 Construct Binary Tree from Preorder and Postorder Traversal

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

概述

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

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