LeetCode 199 二叉树的右视图(dfs)

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

示例:

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

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

思路

题目要求二叉树的右视图，直接用dfs遍历，那么我们就需要尽量往右找，因为可能右子树遍历完了，左子树的深度还有更深的。需要用一个哈希来记录一下，当前层是不是已经找到了最右边的点，找到了就标记一下，没找到就加入到答案的列表中。最后输出结果即可。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution
{
public:
    vector<pair<int, int>> ans;
    unordered_map<int, int> mp;
    void dfs(TreeNode *node, int deep)
    {
        if (!node)
            return;
        if (mp.find(deep) == mp.end())
        {
            ans.push_back({node->val, deep});
            mp[deep]++;
        }
        if (node->right)
            dfs(node->right, deep + 1);
        if (node->left)
            dfs(node->left, deep + 1);
    }
    vector<int> rightSideView(TreeNode *root)
    {
        dfs(root, 0);
        vector<int> result;
        for (auto [val, deep] : ans)
            result.push_back(val);
        return result;
    }
};

最后修改于 2020-04-22

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。