题解 | BM41 输出二叉树的右视图

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 求二叉树的右视图
 * @param xianxu int整型一维数组 先序遍历
 * @param zhongxu int整型一维数组 中序遍历
 * @return int整型一维数组
 */
function solve(xianxu, zhongxu) {
    // write code here
    let ans = new TreeNode(0);
    // 当前序和中序遍历数组长度不同，则返回空
    if (xianxu.length != zhongxu.length) {
        return null;
    }
    // 当前序和中序遍历数组长度都为0，则返回空
    if (xianxu.length == 0 && zhongxu.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 < zhongxu.length; ++i) {
        node.push({
            // 中序遍历值
            value: zhongxu[i],
            // 对应前序遍历下标
            index: xianxu.findIndex(item => {
                return item == zhongxu[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);
    let list = [];
    // 打印二叉树右视图
    function getRight(node, cnt) {
        if (node == null) {
            return;
        }
        if (node.left) {
            getRight(node.left, cnt + 1);
        }
        if (node.right) {
            getRight(node.right, cnt + 1);
        }
        if (list[cnt]) {
            list[cnt].push(node.val);
        } else {
            list[cnt] = [];
            list[cnt].push(node.val);
        }
    }
    getRight(ans.right, 0);
    let arr = [];
    for (let i = 0; i < list.length; ++i) {
        arr.push(list[i].pop());
    }
    return arr;
}
module.exports = {
    solve: solve
};