Leetcode 199: Binary Tree Right Side View-白红宇

Leetcode 199: Binary Tree Right Side View

阅读量：4150 次

发布时间：2019-05-25

本文共 1152 字，大约阅读时间需要 3 分钟。

Problem:

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.

For example:

Given the following binary tree,

1 <—

/ \

2 3 <—

\ \

5 4 <—

You should return [1, 3, 4].

Credits:

Special thanks to @amrsaqr for adding this problem and creating all test cases.

分析：

其实本题比较简单，Right Side View即输出每一行最右边的一个元素。对树进行层次遍历，输出每层最右边一个元素即可。

算法如下：

0）空集合A、B，以及空的返回集合C。

1）将树根元素加入到集合A。

2）对集合A中的每一个元素，依次取其左、右子节点，加入到集合B。

3）将集合A最右边的一个元素加入到集合C中。

4）交换集合A、B。清空集合B。

5）重复第2、3、4步，直到集合A为空。

6）集合C中存放的元素即为该树的右视图。

代码如下，运行时间为10ms。

class Solution {public:    vector
   
     rightSideView(TreeNode *root) {        vector
    
      result;        vector
     
       hirency;         vector
      
        tmp;        vector
       
         swap;        if (root != NULL)            hirency.push_back(root);        while (hirency.size() >0)        {            for (int i=0; i
        
         left) tmp.push_back(node->left); if(node->right) tmp.push_back(node->right); } result.push_back(hirency.at(hirency.size()-1)->val); hirency.clear(); swap = hirency; hirency = tmp; tmp = swap; } return result; }};