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].
s思路： 1. 树的问题，根本是遍历。这道题，站在右边，看到的是一层一层的，那么用bfs，用queue来存每一层的数，然后把每一层最后一个数输出即可！ 2. 如果非要用dfs来，怎么办？这样的困境，之前也遇到过。回忆一下，发现居然有一个套路，可以让dfs同样实现bfs才能干的活。这个套路是这样的：设置一个level变量来跟踪目前变量所在的层数，如果这个层数比vector的size大，那就说明第一次遇到，那么就需要resize vector来保存这个数；如果这个层数比vector的size小，说明以前遇到过，而且这个数在左侧，因此直接覆盖这个数在vector中的值。这样，最后在vector中留下来的数就是从右侧看到的数。通过描述这个过程，发现dfs每个数都要写一遍在vector中，而bfs只有满足条件的才往里写！ 3. 为啥不让找从左侧看到的树呢？因为太容易了，所有的遍历都是从左边开始。反而，从右边看的视图不容易得到。
//方法1：bfs，queueclass Solution {public: vector<int> rightSideView(TreeNode* root) { // vector<int> res; if(!root) return res; queue<TreeNode*> QQ; TreeNode* cur=root; qq.push(cur); while(!qq.empty()){ int sz=qq.size(); for(int i=0;i<sz;i++){ cur=qq.front(); qq.pop(); if(i==sz-1) res.push_back(cur->val); if(cur->left) qq.push(cur->left); if(cur->right) qq.push(cur->right); } } return res; }};//方法2：dfs，recursive,in-orderclass Solution {public: void helper(TreeNode* root,vector<int>&res,int level){ if(!root) return; if(res.size()<level+1){ res.resize(level+1); } res[level]=root->val; //根 helper(root->left,res,level+1);//左 helper(root->right,res,level+1);//右 } vector<int> rightSideView(TreeNode* root) { // vector<int> res; helper(root,res,0); return res; }};新闻热点
疑难解答
