leetcode-0105 从前序与中序遍历序列构造二叉树

[GuoLizhi]

递归 分治算法

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
var buildTree = function(preorder, inorder) {
    return buildTreeHelper(preorder, 0, preorder.length, inorder, 0, inorder.length);
};
var buildTreeHelper = function(preorder, pStart, pEnd, inorder, iStart, iEnd) {
    if (pStart === pEnd) {
        return null;
    }
    const rootVal = preorder[pStart];
    const root = new TreeNode(rootVal);
    // 在中序遍历中找到根节点的位置
    let iRootIndex = 0;
    for (let i = iStart; i < iEnd; i++) {
        if (rootVal === inorder[i]) {
            iRootIndex = i;
            break;
        }
    }
    const leftNum = iRootIndex - iStart;
    // 递归构造左子树
    root.left = buildTreeHelper(preorder, pStart+1, pStart+leftNum+1, inorder, iStart, iRootIndex);
    root.right = buildTreeHelper(preorder, pStart+leftNum+1, pEnd, inorder, iRootIndex+1, iEnd);
    return root;
}