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

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 求二叉树的右视图
 * @param xianxu int整型一维数组 先序遍历
 * @param zhongxu int整型一维数组 中序遍历
 * @return int整型一维数组
 */
function solve(xianxu, zhongxu) {
    // write code here
    // 1. 先构造树结构，数组存储的方式有点难
    const root = buildTree(xianxu, zhongxu);
    // 2. 层序遍历
    const cengxu = traverseTree(root);
    // 3. rightView
    const res = rightView(cengxu);
    return res;
}

function rightView(vector) {
    const res = [];
    for(let i = 0; i < vector.length; i++) {
        const lastindex = vector[i].length - 1;
        res.push(vector[i][lastindex]);
    }
    return res;
}


// 层序遍历 需要依赖一个队列
function traverseTree(root) {
    if (!root) return;
    const queue = [],
        res = [];

    queue.push(root);

    while (queue.length) {
        let size = queue.length;
        const temp = [];
        while (size--) {
            const node = queue.shift();
            temp.push(node.val);

            if (node.left) {
                queue.push(node.left);
            }

            if (node.right) {
                queue.push(node.right);
            }
        }
        res.push(temp);
    }
    return res;
}

function buildTree(xianxu, zhongxu) {
    if (xianxu.length === 0) return;

    const root = {
        val: xianxu[0],
        left: undefined,
        right: undefined,
    };

    const rootInZhongIndex = zhongxu.findIndex((i) => i === root.val);

    const zleft = zhongxu.slice(0, rootInZhongIndex);
    const xleft = xianxu.slice(1, zleft.length + 1);
    root.left = buildTree(xleft, zleft);

    const xright = xianxu.slice(1 + xleft.length);
    const zright = zhongxu.slice(rootInZhongIndex + 1);
    root.right = buildTree(xright, zright);

    return root;
}

module.exports = {
    solve: solve,
};

给出一颗二叉树的前序和中序，可以构造出二叉树的结构。

打印二叉树的右视图就是打印二叉树层序遍历的最右边的数据。

构造二叉树结构，最简单的还是用树的链式结构，这样方便利用递归，解法逻辑简单。

层序遍历由于二叉树的结构，导致如果是遍历二叉树没办法同时保持左子树和右子树的值，同时还知道此时处于哪一层。所以而二叉树层序遍历需要依赖一个队列queue，每次把节点的值放入队列，记录当前队列的大小，每次从queue中取size大小的数出来，再将节点的左节点和右节点放入队列，循环往复，直至队列queue中没有值，我们就层序遍历完所有层了。文字有点乱的话，看一下traverseTree的代码就更好理解了。

总结，这道题我的做法就是：

1. 构造（还原）二叉树
2. 层序遍历二叉树
3. 打印右视图