Day334:按要求实现 rightView 函数

[Genzhen]

function TreeNode(val){
  this.val = val;
  this.left = null;
  this.right = null;
}
function rightView(root){
  // 请你实现
}
// => [1,4,3]
     1      => 1
   2   4    => 4
 7   3      => 3

---

每日一题会在下午四点在交流群集中讨论，五点小程序中更新答案 欢迎大家在下方发表自己的优质见解

二维码加载失败可点击 小程序二维码

扫描下方二维码，收藏关注，及时获取答案以及详细解析，同时可解锁800+道前端面试题。

---

代码实现

题目的思路很明显，对二叉树进行层序遍历，然后取得每一层的最后一个节点。放到一个数组里最后返回。

• 可以设置一个队列存放依次遍历的节点对象。
• 使用两层循环
  • 内层循环通过不断出队列的方式遍历当前层的节点，同时通过左右链接收集下一层节点
  • 外层循环判断队列长度>0 时就继续运行，从而实现逐层迭代

function rightView(root) {
  if (!root) return [];
  const queue = [];
  const arrRS = [];
  // 先保存根结点，也就是第一层二叉树
  queue.push(root);
  while (queue.length > 0) {
    // 将队列长度先保存到一个变量里面
    // 表示的是上一层的节点的数量
    let length = queue.length;
    let temp = null;
    // 遍历上一层节点，将它们的子节点加入队列中，收集得到二叉树的下一层
    for (let i = 0; i < length; i++) {
      // 出队列，并获得返回的父节点
      const node = queue.shift();
      // 每次都用当前节点的val覆盖temp
      // temp最后会等于当前层最右的一个非空节点的val值
      if (node.val) temp = node.val;
      // 收集当前节点的左节点和右节点，从而得到下一层
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    // 收集每一层的最右节点
    arrRS.push(temp);
  }
  return arrRS;
}

[whenTheMorningDark]

bfs(value) {
      const result = []
      let level = 0
      const stack = [value]
      while (stack.length > 0) {
        const levelSize = stack.length
        for (let i = 0; i < levelSize; i++) {
          const node = stack.shift()
          if (level === result.length) {
            result.push(node.val)
          }
          if (node.right) {
            stack.push(node.right)
          }
          if (node.left) {
            stack.push(node.left)
          }
        }
        level++
      }
      return result
    }
let value =  {
        val: '1',
        left: {
          val: '2',
          left: {
            val: '7'
          },
          right: {
            val: '3'
          }
        },
        right: {
          val: '4',
          left: {
            val: '3'
          }
        }
      }
console.log(bfs(value)) // [1,4,3]

[DaphnisLi]

const rightView = (root) => {
  const queue = [root]
  const res = []
  while (queue.length) {
    let len = queue.length
    while (len--) {
      const node = queue.shift()
      if (!len) {
        res.push(node.val)
      }
      if (node.left) {
        queue.push(node.left)
      }
      if (node.right) {
        queue.push(node.right)
      }
    }
  }
  return res
}