105. 从前序与中序遍历序列构造二叉树

给定一棵树的前序遍历 preorder 与中序遍历 inorder。请构造二叉树并返回其根节点。

示例 1:

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

示例 2:

Input: preorder = [-1], inorder = [-1]
Output: [-1]

解题思路

方法与106. 从中序与后序遍历序列构造二叉树一样

代码

C++

class Solution {
public:
    unordered_map<int, int> inorderMap;
    vector<int> pre;
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        for (int i = 0; i < inorder.size(); i++) {
            // 将中序遍历的节点值和索引记录在哈希表中
            inorderMap.insert(pair<int,int>(inorder[i],i));
        }
        pre = preorder;
        return getTree(0, inorder.size() - 1, 0, preorder.size() - 1);
    }

    TreeNode* getTree(int is, int ie, int ps, int pe){
        if (is > ie || ps > pe) return nullptr;
        int nodeVal = pre[ps]; //前序遍历的第一个节点值，即当前的根节点的值
        int ri = inorderMap[nodeVal]; //找到根节点在中序遍历中的位置
        TreeNode* node =new TreeNode(nodeVal);
        node->left = getTree(is, ri - 1, ps + 1, ps + ri -is);
        node->right = getTree(ri + 1, ie, ps + ri - is + 1, pe);
        return node;
    }
};

JavaScript

let inorderMap = {};
let pre = [];

/**
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
var buildTree = function(preorder, inorder) {
    for (let i = 0; i < inorder.length; i++) {
        inorderMap[inorder[i]] = i;
    }
    pre = preorder;
    return getTree(0, inorder.length - 1, 0, preorder.length - 1);
};

function getTree(is, ie, ps, pe) {
    if (is > ie || ps > pe) return null;
    let nodeVal = pre[ps];
    let ri = inorderMap[nodeVal];
    let node = new TreeNode(nodeVal);
    node.left = getTree(is, ri - 1, ps + 1, ps + ri - is);
    node.right = getTree(ri + 1, ie, ps + ri - is + 1, pe);
    return node;
}