【JS】输出二叉树的右视图

function TreeNode(val) {
  this.val = val;
  this.left = this.right = null;
}

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 求二叉树的右视图
 * @param xianxu int整型一维数组 先序遍历
 * @param zhongxu int整型一维数组 中序遍历
 * @return int整型一维数组
 */
function solve( xianxu , zhongxu ) {

  // 记录中序 val => idx
  let inOrder = new Map();
  for (let i = 0; i < zhongxu.length; i++) {
    inOrder.set(zhongxu[i], i);
  }

  // 重建二叉树
  function rebuildTree(preIdx, inLeft, inRight) {
    if (inLeft > inRight) return null;
    let val = xianxu[preIdx];
    let node = new TreeNode(val);
    let inIdx = inOrder.get(val);
    if (inLeft < inRight) {
      node.left = rebuildTree(preIdx + 1, inLeft, inIdx - 1);
      node.right = rebuildTree(preIdx + (inIdx - inLeft + 1), inIdx + 1, inRight);
    }
    return node;
  }

  let root = rebuildTree(0, 0, zhongxu.length - 1);
  let queue = [root];
  let res = [];

  // bfs
  while (queue.length) {
    let len = queue.length;
    let isPush = false;
    // 对于每一层做一次处理
    while (len--) {
      let node = queue.shift();
      // 只push一个值，因为是右视图
      if (!isPush) {
        res.push(node.val);
        isPush = true;
      }
      // 既然是右视图，那就是右节点优先
      node.right && queue.push(node.right);
      node.left && queue.push(node.left);
    }
  }

  return res;
}

module.exports = {
    solve : solve
};