1. 广度优先遍历

  • 广度优先遍历出每一层的节点
  • 取每层节点最右的值push到result中
  1. /*
  2.  * @lc app=leetcode.cn id=199 lang=javascript
  3.  *
  4.  * [199] 二叉树的右视图
  5.  */
  7. // @lc code=start
  8. /**
  9.  * Definition for a binary tree node.
  10.  * function TreeNode(val) {
  11.  *     this.val = val;
  12.  *     this.left = this.right = null;
  13.  * }
  14.  */
  15. /**
  16.  * @param {TreeNode} root
  17.  * @return {number[]}
  18.  */
  19. var rightSideView = function (root) {
  20.   if (!root) return []
  22.   const result = []
  23.   const queue = []
  25.   queue.push(root)
  27.   while (queue.length) {
  28.     let len = queue.length
  29.     result.push(queue[0].val)
  31.     while (len--) {
  32.       const node = queue.shift()
  34.       if (node.right) queue.push(node.right)
  35.       if (node.left) queue.push(node.left)
  36.     }
  37.   }
  38.   return result
  39. }
  40. // @lc code=end

时间复杂度：

  • 每个节点都被遍历到一次所以 时间复杂度为 O(n)

**
空间复杂度:

  • 每个节点最多进队列一次，所以队列长度最大不不超过 nn，所以这里的空间代价为 O(n)

2. 深度优先遍历

  • 根节点开始优先遍历右序列
  • 因为是右序列优先遍历，所以每层的第一个节点就是所能看见的节点
  1. /*
  2.  * @lc app=leetcode.cn id=199 lang=javascript
  3.  *
  4.  * [199] 二叉树的右视图
  5.  */
  7. // @lc code=start
  8. /**
  9.  * Definition for a binary tree node.
  10.  * function TreeNode(val) {
  11.  *     this.val = val;
  12.  *     this.left = this.right = null;
  13.  * }
  14.  */
  15. /**
  16.  * @param {TreeNode} root
  17.  * @return {number[]}
  18.  */
  19. var rightSideView = function (root) {
  20.   if (!root) return []
  21.   const result = []
  22.   DFS(root, 0, result)
  23.   return result
  24. }
  26. const DFS = function (node, level, result) {
  27.   if (level >= result.length) {
  28.     result.push(node.val)
  29.   }
  30.   level++
  31.   if (node.right) DFS(node.right, level, result)
  32.   if (node.left) DFS(node.left, level, result)
  33. }
  34. // @lc code=end

时间复杂度：

  • 每个节点都被遍历了一次所以为 O(n)


空间复杂度：**

  • 二叉树的结构未知，最差的情况会退化成一条链表，所以空间复杂度为 O(n)