题解 | BM40 重建二叉树

/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */
function reConstructBinaryTree(pre, vin) {
    // write code here
    let ans = new TreeNode(0);
    // 当前序和中序遍历数组长度不同，则返回空
    if (pre.length != vin.length) {
        return null;
    }
    // 当前序和中序遍历数组长度都为0，则返回空
    if (pre.length == 0 && vin.length == 0) {
        return null;
    }
    let node = [];
    // 可以根据每一层的根节点将中序遍历分割为左右节点数组
    /**
     *  先序    1	2	4	7	3	5	6	8
     *  下标    0	1	2	3	4	5	6	7
     * 
     *  层数    3	4	2	1	3	2	4	3
     *  中序    4	7	2	1	5	3	8	6
     *  下标    2	3	1	0	5	4	7	6
     */
    // 处理数据：在中序遍历数组中找到前序遍历对应下标
    for (let i = 0; i < vin.length; ++i) {
        node.push({
            // 中序遍历值
            value: vin[i],
            // 对应前序遍历下标
            index: pre.findIndex(item => {
                return item == vin[i]
            })
        })
    }
    // 重新构造二叉树
    function rebuildNode(node, ans) {
        // 若无节点则直接返回
        if (node.length < 1) {
            return;
        }
        // index为最小下标对应中序序遍历下标，min为最小下标
        let index = -1, min = 1000007, len = node.length;
        for (let i = 0; i < len; ++i) {
            let cur = node[i];
            if (min > cur.index) {
                min = cur.index;
                index = i;
            }
        }
        // 只需要给当前节点赋值即可
        ans.val = node[index].value;
        if (index < len) {
            // 分割左右节点数组
            let l = node.slice(0, index), r = node.slice(index + 1);
            // console.log("l:", l);
            // console.log("r:", r);
            if (l.length > 0) {
                ans.left = new TreeNode(0);
                rebuildNode(l, ans.left);
            }
            if (r.length > 0) {
                ans.right = new TreeNode(0);
                rebuildNode(r, ans.right);
            }
        }
        return;
    }
    // 将答案挂载到右节点
    ans.right = new TreeNode(0);
    rebuildNode(node, ans.right);
    return ans.right;
}
module.exports = {
    reConstructBinaryTree: reConstructBinaryTree
};