Heading

[106.从中序与后序遍历序列构造二叉树] https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/description/

Tags: algorithms microsoft array tree depth-first-search

Langs: c cpp csharp golang java javascript kotlin php python python3 ruby rust scala swift typescript

• algorithms
• Medium (70.72%)
• Likes: 410
• Dislikes: -
• Total Accepted: 78.8K
• Total Submissions: 111.3K
• Testcase Example: '[9,3,15,20,7]\n[9,15,7,20,3]'

根据一棵树的中序遍历与后序遍历构造二叉树。

注意:
你可以假设树中没有重复的元素。

例如，给出

中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]

返回如下的二叉树：

    3
   / \
  9  20
    /  \
   15   7

/*
 * @lc app=leetcode.cn id=106 lang=javascript
 *
 * [106] 从中序与后序遍历序列构造二叉树
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {number[]} inorder
 * @param {number[]} postorder
 * @return {TreeNode}
 */
var buildTree = function(inorder, postorder) {
    const IndexInorder = {};//字符在中序序列中的下标
    inorder.forEach((val, idx) => IndexInorder[val] = idx);
    const n = postorder.length;
    const fn = (postLeft, postRight, inLeft, inRight) => {
        if (postLeft > postRight) return null;
        const p = new TreeNode(postorder[postRight]),//创建根节点
            indexRoot = IndexInorder[postorder[postRight]],//根节点位置
            leftSubTreeSize = indexRoot - inLeft;//左子树长度
        p.left = fn(postLeft, postLeft + leftSubTreeSize -1, inLeft, indexRoot - 1);
        p.right = fn(postLeft + leftSubTreeSize, postRight-1, indexRoot + 1, inRight);
        return p
    }

    return fn(0, n - 1, 0, n - 1);
};
// @lc code=end