LeetCode 105 Construct Binary Tree from Preorder and Inorder Traversal

概述

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

迭代法

前序给出根节点和左子节点，之后根据中序得知左子树的元素个数，进而再通过前序知道右子节点。

然后迭代下去。

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

Links: leetcode-105-construct-binary-tree-from-preorder-and-inorder-traversal

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