leetcode106题

思路

根据中序遍历和后序遍历的特性可知，后序遍历的最后一个元素为根元素。然后找到中序遍历中对应的序号。将中序遍历的划分为两部分，左边为左子树，右边为右子树。

方法

由思路可知，可以使用递归。递归函数的入口为划分的区间。left表示左端点，right表示右端点。

1. 如果left和right相等说明当前节点没有左右孩子直接返回一个新的树节点。
2. 设置一个count表示当前访问后序遍历中的元素。
3. 设置一个索引值，表示后序遍历中元素在中序中的位置。
4. 然后取postorder[count]，遍历中序列表找到这个索引。
5. 根据索引生成根节点。
6. 递归左右子树。
7. 遍历完成，返回节点。

代码

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {number[]} inorder
 * @param {number[]} postorder
 * @return {TreeNode}
 */
var buildTree = function (inorder, postorder) {
    let count = postorder.length
    const iter = function (left, right) {
        if (count <= 0) return
        count--
        if (left === right) {
            return new TreeNode(inorder[left])
        }
        let index
        for (let i = left; i <= right; i++) {
            if (inorder[i] === postorder[count]) {
                index = i
                break
            }
        }
        const node = new TreeNode(postorder[count])
        if(right >= index + 1)
        node.right = iter(index + 1, right)
        if(index - 1 >= left)
        node.left = iter(left, index - 1)
        return node
    }
    return iter(0, inorder.length - 1)
};