Leetcode 199. 二叉树的右视图

题目

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

示例:

输入: [1,2,3,null,5,null,4]
输出: [1, 3, 4]
解释:

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

解题思路

利用二叉树的层次遍历，然后去每一个层次遍历的最后一个数据即可。

C++解法

#include <iostream>
#include <vector>
#include <map>
#include <set>
using namespace std;
struct TreeNode {
     int val;
     TreeNode *left;
     TreeNode *right;
     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
    vector<vector<int>> items;
    vector<int> rightSideView(TreeNode* root) {
        vector<int> result;
        items.clear();
        result.clear();
        travel(root, 0);
        for (auto item: items) {
            result.push_back(item[item.size() - 1]);
        }
        return result;
    }
    
    void travel(TreeNode * root, int depth) {
        if (root == NULL) return;
        if (depth == items.size()) items.push_back({});
        items[depth].push_back(root->val);
        if (root->left) travel(root->left, depth + 1);
        if (root->right) travel(root->right, depth + 1);
    }
};
int main(int argc, const char * argv[]) {
    // insert code here...
    Solution solution;
    TreeNode * node = new TreeNode(1);
    node->left = new TreeNode(2);
    node->right = new TreeNode(3);
    node->left->right = new TreeNode(5);
    node->right->right = new TreeNode(4);
    auto result = solution.rightSideView(node);
    for (auto item: result) cout << item << " ";
    cout << endl;
    return 0;
}

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-right-side-view