二叉树的右视图

问题描述

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

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

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

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

思路

和层次遍历的思路是一样的

• 按层将二叉树存到vector<vector<int>> vec中，此处和二叉树的层次遍历不同的是，本题从每层的右侧开始存。
  当然也可以从每层的左边开始遍历，用reverse反转一下就可以了。
• 将veci存到vector<int> ret中。
• 最后return ret即可。

题解

/**
 * 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<vector<int>> vec;
    vector<int> ret;

    vector<int> rightSideView(TreeNode *root) {
        dfs(root, 0);
        int n = vec.size();
        if (n == 0) return ret;
        for(int i=0;i<n;i++){
            ret.push_back(vec[i][0]);
        }
        return  ret;
    }

    void dfs(TreeNode *node, int level) {
        if (node == nullptr) return;
        if (level + 1 > vec.size()) vec.push_back(vector<int>());
        vec[level].push_back(node->val);
        dfs(node->right, level + 1);
        dfs(node->left, level + 1);
    }
};