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來存每一層的數(shù)，然后把每一層最后一個數(shù)輸出即可！ 2. 如果非要用dfs來，怎么辦？這樣的困境，之前也遇到過。回憶一下，發(fā)現(xiàn)居然有一個套路，可以讓dfs同樣實現(xiàn)bfs才能干的活。這個套路是這樣的：設(shè)置一個level變量來跟蹤目前變量所在的層數(shù)，如果這個層數(shù)比vector的size大，那就說明第一次遇到，那么就需要resize vector來保存這個數(shù)；如果這個層數(shù)比vector的size小，說明以前遇到過，而且這個數(shù)在左側(cè)，因此直接覆蓋這個數(shù)在vector中的值。這樣，最后在vector中留下來的數(shù)就是從右側(cè)看到的數(shù)。通過描述這個過程，發(fā)現(xiàn)dfs每個數(shù)都要寫一遍在vector中，而bfs只有滿足條件的才往里寫！ 3. 為啥不讓找從左側(cè)看到的樹呢？因為太容易了，所有的遍歷都是從左邊開始。反而，從右邊看的視圖不容易得到。
//方法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; }};新聞熱點
疑難解答
