199.binary-tree-right-side-view.md

题目地址

https://leetcode.com/problems/binary-tree-right-side-view/description/

题目描述

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

Example:

Input: [1,2,3,null,5,null,4]
Output: [1, 3, 4]
Explanation:

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

思路

这道题和 leetcode 102 号问题《102.binary-tree-level-order-traversal》很像

这道题可以借助队列实现，首先把 root 入队，然后入队一个特殊元素 Null(来表示每层的结束)。

然后就是 while(queue.length), 每次处理一个节点，都将其子节点（在这里是 left 和 right）放到队列中。

然后不断的出队， 如果出队的是 null，则表式这一层已经结束了，我们就继续 push 一个 null。

关键点解析

• 队列

• 队列中用 Null(一个特殊元素)来划分每层

• 树的基本操作- 遍历 - 层次遍历（BFS）

• 二叉树的右视图可以看作是层次遍历每次只取每一层的最右边的元素

代码

• 语言支持：JS，C++

Javascript Code:

/*
 * @lc app=leetcode id=199 lang=javascript
 *
 * [199] Binary Tree Right Side View
 *
 * https://leetcode.com/problems/binary-tree-right-side-view/description/
 *
 * algorithms
 * Medium (46.74%)
 * Total Accepted:    156.1K
 * Total Submissions: 332.3K
 * Testcase Example:  '[1,2,3,null,5,null,4]'
 *
 * Given a binary tree, imagine yourself standing on the right side of it,
 * return the values of the nodes you can see ordered from top to bottom.
 *
 * Example:
 *
 *
 * Input: [1,2,3,null,5,null,4]
 * Output: [1, 3, 4]
 * Explanation:
 *
 * ⁠  1            <---
 * ⁠/   \
 * 2     3         <---
 * ⁠\     \
 * ⁠ 5     4       <---
 *
 */
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var rightSideView = function(root) {
  if (!root) return [];

  const ret = [];
  const queue = [root, null];

  let levelNodes = [];

  while (queue.length > 0) {
    const node = queue.shift();
    if (node !== null) {
      levelNodes.push(node.val);
      if (node.right) {
        queue.push(node.right);
      }
      if (node.left) {
        queue.push(node.left);
      }
    } else {
      // 一层遍历已经结束
      ret.push(levelNodes[0]);
      if (queue.length > 0) {
        queue.push(null);
      }
      levelNodes = [];
    }
  }

  return ret;
};

C++ Code:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        auto ret = vector<int>();
        if (root == nullptr) return ret;
        auto q = queue<const TreeNode*>();
        q.push(root);
        while (!q.empty()) {
            auto sz = q.size();
            for (auto i = 0; i < sz; ++i) {
                auto n = q.front();
                q.pop();
                if (n->left != nullptr ) q.push(n->left);
                if (n->right != nullptr ) q.push(n->right);
                if (i == sz - 1) ret.push_back(n->val);
            }
        }
        return ret;
    }
};

扩展

假如题目变成求二叉树的左视图呢？

很简单我们只需要取 queue 的最后一个元素即可。 或者存的时候反着来也行

其实我们没必要存储 levelNodes，而是只存储每一层最右的元素，这样空间复杂度就不是 n 了， 就是 logn 了。