LeetCode题解199.binary-tree-right-side-view

题目地址

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 了。

LeetCode题解124.binary-tree-maximum-path-sum

题目地址 https://leetcode.com/problems/binary-tree-maximum-path-sum/description/ 题目描述 Given a non-empty binary tree, find the maximum path sum. For this problem, a path is defined as a…

LeetCode题解1104.path-in-zigzag-labelled-binary-tree

题目地址 https://leetcode-cn.com/problems/path-in-zigzag-labelled-binary-tree/description/ 题目描述 在一棵无限的二叉树上，每个节点都有两个子节点，树中的节点 逐行 依次按 “之” 字形进行标记。 如下图所示，在奇数行（即，第一行、第三行、第五行……）中，按从左到右的顺序进行标…

LeetCode题解145.binary-tree-postorder-traversal

题目地址 https://leetcode.com/problems/binary-tree-postorder-traversal/description/ 题目描述 Given a binary tree, return the postorder traversal of its nodes' values. For example: Given bi…

LeetCode题解144.binary-tree-preorder-traversal

题目地址 https://leetcode.com/problems/binary-tree-preorder-traversal/description/ 题目描述 Given a binary tree, return the preorder traversal of its nodes' values. Example: Input: [1,null…

LeetCode题解104.maximum-depth-of-binary-tree

题目地址 https://leetcode.com/problems/maximum-depth-of-binary-tree/description/ 题目描述 Given a binary tree, find its maximum depth. The maximum depth is the number of nodes along the lo…