199. 二叉树的右视图

题目描述

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

示例 1：

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

输出：[1,3,4]

示例 2：

输入：root = [1,null,3]

输出：[1,3]

示例 3：

输入：root = []

输出：[]

提示：

• 二叉树的节点个数的范围是 [0,100]
• -100 <= Node.val <= 100

出处：LeetCode

解法一：层序遍历

思路

层序遍历二叉树，每层最后一个节点即为所求。

实现

function rightSideView(root: TreeNode | null): number[] {
  if (root === null) {
    return [];
  }
  const queue: TreeNode[] = [root];
  const result: number[] = [];
  while (queue.length) {
    const size = queue.length;
    for (let i = 0; i < size; i++) {
      const node = queue.shift()!;
      if (i === size - 1) {
        result.push(node.val);
      }
      if (node.left) {
        queue.push(node.left);
      }
      if (node.right) {
        queue.push(node.right);
      }
    }
  }
  return result;
}

复杂度分析

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

解法二：DFS

思路

递归遍历二叉树，记录每层最后一个节点的值。

实现

function rightSideView(root: TreeNode | null): number[] {
  const result: number[] = [];
  const dfs = (node: TreeNode | null, depth: number) => {
    if (node === null) {
      return;
    }
    if (depth === result.length) {
      result.push(node.val);
    }
    dfs(node.right, depth + 1);
    dfs(node.left, depth + 1);
  };
  dfs(root, 0);
  return result;
}

复杂度分析

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