199. Binary Tree Right Side View侧面观察二叉树

qlmx
qlmx
qlmx
50
文章
2
评论
2020年2月15日00:16:38 评论 780阅读3分2秒

199. Binary Tree Right Side View(侧面观察二叉树)

1 问题描述

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

2 解析

从二叉树的右侧观察它,将观察到的节点按照 从上到下的顺序输出,就是求 层次遍历二叉树,每个层中的最后一个节点。

![屏幕快照 2019-03-28 23.26.25](/Users/QLMX/Files/Blog/algorithm/img/屏幕快照 2019-03-28 23.26.25.png)

3 C++实现

//使用队列进行层次遍历
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> result;
        queue<pair<TreeNode *, int>> Q;

        if(!root)
            return result;

        Q.push(make_pair(root, 0));
        while(!Q.empty()) {
            pair<TreeNode*, int> item;
            item = Q.front();
            Q.pop();
            TreeNode* node = item.first;
            int index = item.second;

            if(result.size() == index)
                result.push_back(node->val);
            else
                result[index] = node->val;

            if(node->left)
                Q.push(make_pair(node->left, index+1));
            if(node->right)
                Q.push(make_pair(node->right, index+1));
        }
        return result;
    }
};
继续阅读
  • 我的微信小程序
  • 这是我的微信小程序扫一扫
  • weinxin
  • 我的微信公众号
  • 我的微信公众号扫一扫
  • weinxin
qlmx
  • 本文由 发表于 2020年2月15日00:16:38
  • 除非特殊声明,本站文章均为原创,转载请务必保留本文链接
匿名

发表评论

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: