199. 二叉树的右视图 🟨

题目

LeetCode 中等

题目

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

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

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

题解

方法：广度优先

BFS 队列

每一层最后一个节点

时间复杂度：O(n)
空间复杂度：O(n)

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val
    this.left = left
    this.right = right
  }
}

function rightSideViewBFS(root) {
  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(
        'node',
        node.val,
        'queue',
        queue.map(i => i.val),
      )
    }

    console.log('📌 层遍历结束', vals)
  }

  return vals
}

const tree = new TreeNode(1)
tree.left = new TreeNode(2, null, new TreeNode(5))
tree.right = new TreeNode(3, null, new TreeNode(4))

console.log('🌰', JSON.stringify(rightSideViewBFS(tree)))

执行结果

♻️ [1]
node 1 queue [2,3]
📌 层遍历结束 [1]
♻️ [2,3]
node 2 queue [3,5]
node 3 queue [5,4]
📌 层遍历结束 [1,3]
♻️ [5,4]
node 5 queue [4]
node 4 queue []
📌 层遍历结束 [1,3,4]
🌰 [1,3,4]

方法：深度优先

DFS 递归

根右左，每一层的第一个结点

时间复杂度：O(n)
空间复杂度：O(n)

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val
    this.left = left
    this.right = right
  }
}

function rightSideViewDFS(root) {
  if (!root) return []

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

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

  return res
}

const tree = new TreeNode(1)
tree.left = new TreeNode(2, new TreeNode(4, new TreeNode(5)))
tree.right = new TreeNode(3)

console.log('🌰', JSON.stringify(rightSideViewDFS(tree)))

执行结果

♻️ node: 1 depth: 0
res: [1]
♻️ node: 3 depth: 1
res: [1,3]
♻️ node: 2 depth: 1
♻️ node: 4 depth: 2
res: [1,3,4]
♻️ node: 5 depth: 3
res: [1,3,4,5]
🌰 [1,3,4,5]

本页目录