LeetCode 105 Construct Binary Tree from Preorder and Inorder Traversal

Tag: 二叉树 LeetCode Posted on 2022-02-06 20:47:44 Edited on 2022-02-06 21:29:51 Views: 161

概述

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

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