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

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 求二叉树的右视图
 * @param xianxu int整型一维数组 先序遍历
 * @param zhongxu int整型一维数组 中序遍历
 * @return int整型一维数组
 */
function solve(preOrderArr,  inOrderArr) {
    if (preOrderArr.length === 0) return [];
    
    // 建树
    function buildTree(preOrderArr,  inOrderArr) {
        // 终止条件
        if (preOrderArr.length === 0) return null;
        // 先序遍历【根节点】【左 子 树】【右 子 树】
        // 中序遍历【左 子 树】【根节点】【右子树】     
        const rootVal = preOrderArr[0]; // 先序遍历的第一个节点既是根节点
        const inOrderRootIndex = inOrderArr.findIndex(num => num === rootVal); // 获取中序遍历的根节点索引
        const leftTreeCount = inOrderRootIndex; // 中序遍历左侧都是左子树节点
        
        const root = new TreeNode(rootVal); // 创建根节点
        
        // 求出前序遍历左子树范围和中序遍历左子树返回，进行递归
        const preOrderLeftTree = preOrderArr.slice(1, leftTreeCount + 1);
        const inOrderLeftTree = inOrderArr.slice(0, inOrderRootIndex);
        root.left = buildTree(preOrderLeftTree, inOrderLeftTree)
        
        // 求出前序遍历右子树范围和中序遍历右子树返回，进行递归
        const preOrderRightTree = preOrderArr.slice(leftTreeCount + 1); // slice 包括 begin，不包括 end
        const inOrderRightTree = inOrderArr.slice(inOrderRootIndex + 1); // 中间有根元素，所以加了 1
        root.right = buildTree(preOrderRightTree, inOrderRightTree);
        return root;
    }
    
    const tree = buildTree(preOrderArr,  inOrderArr)
    
    // 层序遍历
    const queue = [tree]; // 使用队列辅助迭代
    const res = [];
    while(queue.length) {
        let levelCount = queue.length; // 单层数量
        while(levelCount--) {
            const node = queue.shift();
            if (levelCount===0) {
                // 如果是最后一个则是右视图可见元素，推出数组中
                res.push(node.val)
            }
            if (node.left) {
                queue.push(node.left)
            }
            if (node.right) {
                queue.push(node.right)
            }
        }
    }
    
    return res;
}
module.exports = {
    solve : solve
};