leetcode-199

leetcode 199

/**
* 2019:10:24
* leetcode-cn-199
* icenaive
*/

/**
* 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<int> rightSideView(TreeNode* root) {
       queue<TreeNode *> q;
       vector<int> res;
       if(root) q.push(root);
       while(!q.empty()) {
           int cnt = q.size();
           for(int i = 0;i < cnt;i++) {
               TreeNode *temp = q.front(); q.pop();
               if(cnt - 1 == i) res.push_back(temp->val);    // 最后一个节点
               if(temp->left) q.push(temp->left);
               if(temp->right) q.push(temp->right);
           }
       }
       return res;
   }
};


// 递归解法
// 修改先序遍历为根-右-左 这样每次遍历时每层第一个节点如结果数组就可以
class Solution {
private:
   vector<int> res;
   void dfs(TreeNode *root, int level) {
       if(!root) return ; // 递归边界
       if(level == res.size()) res.push_back(root->val);
       if(root-right) dfs(root->right, level + 1);
       if(root->left) dfs(root->left, level + 1);
   }
public:
   vector<int> rightSideView(TreeNode* root) {
       if(!root) return res;
       dfs(root, 0);
       return res;
   }
};