zhangdizhangdi

199.二叉树的右视图

题目

LeetCode 中等

题目

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

示例：
输入: [1,2,3,null,5,null,4]
输出: [1,3,4]

题解

方法：广度优先

BFS 队列 O(n) O(n)

ts
//BFS，每一层最后一个节点
function rightSideViewBFS(root: TreeNode | null): number[] {
  if (!root) return []

  const vals = []
  const queue = [root]
  while (queue.length) {
    console.log(queue.map(i => i.val))

    let len = queue.length
    while (len) {
      let node = queue.shift()
      if (len === 1) vals.push(node.val)
      if (node.left) queue.push(node.left)
      if (node.right) queue.push(node.right)
      len--

      console.log(queue.map(i => 'while - ' + i.val))
    }

    console.log('当前输出 ---', vals)
  }

  return vals
}

const tree = new Tree([1, 2, 3, null, 5, null, 4])
console.log('🌰', rightSideViewBFS(tree.root))

方法：深度优先

DFS 递归 O(n) O(n)

ts
//DFS，根右左，每一层的第一个结点
function rightSideViewDFS(root: TreeNode | null): number[] {
  if (!root) return []

  let res = []
  const dfs = (node: TreeNode, depth: number) => {
    console.log('node:', node?.val, 'depth:', depth, res)

    if (depth === res.length) {
      res.push(node.val)
    }
    depth++
    if (node.right) dfs(node.right, depth)
    if (node.left) dfs(node.left, depth)
  }
  dfs(root, 0)

  return res
}

const tree = new Tree([1, 2, 3, null, 5, null, 4])
console.log('🌰', rightSideViewDFS(tree.root))