题目链接

题目描述：

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

示例:

输入: [1,2,3,null,5,null,4]
输出: [1, 3, 4]
解释:
199二叉树的右视图 - 图1

解题思路

执行用时，内存消耗相差无几

  1. BFS用队列实现。根据队列先进先出的特点，每一层最后一个结点即为最右端点。所以，只需在遍历的同时，获取每一层倒数第一个结点即可。
  2. DFS用非递归栈和set实现。DFS顺序为根右左，也就是说每一层出现的第一个结点即为最右端点。所以，可以用set记录层数来判断该层数是否第一次出现，同时栈的存储类型采用pair数据对存放模拟递归的命令结构体Commend和当前结点所处层数level，如果是第一次出现，说明该结点为最右端点。至于非递归实现部分，采用Commend结构体模拟递归时系统栈的运作方式及先后顺序，也就是说“根左右”在系统栈的执行顺序会是“右左根”。

代码

BFS

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  8.  * };
  9.  */
  10. class Solution {
  11. public:
  12.     vector<int> rightSideView(TreeNode* root) {
  13.         vector<int> result;
  14.         if(!root)
  15.             return result;
  16.         queue<TreeNode*> queue_Tree;
  17.         queue_Tree.push(root);
  18.         while(!queue_Tree.empty()){
  19.             int n = queue_Tree.size();
  20.             for(int i = 0; i < n; i++){
  21.                 TreeNode* node = queue_Tree.front();
  22.                 queue_Tree.pop();
  24.                 if(node->left)
  25.                     queue_Tree.push(node->left);
  26.                 if(node->right)
  27.                     queue_Tree.push(node->right);
  29.                 if(i == n - 1)
  30.                     result.push_back(node->val);
  31.             }
  32.         }
  33.         return result;
  34.     }
  35. };

DFS

  1. struct Commend{
  2.     string s; //go,print
  3.     TreeNode* node;
  4.     Commend(string s, TreeNode* node) : s(s), node(node) {}
  5. };
  7. class Solution {
  8. public:
  9.     vector<int> rightSideView(TreeNode* root) {
  10.         vector<int> result;
  11.         unordered_set<int> record;
  12.         if(!root)
  13.             return result;
  15.         stack<pair<Commend,int>> stack_Tree;
  16.         stack_Tree.push(make_pair(Commend("go",root),0));
  18.         while(!stack_Tree.empty()){
  19.             int n = stack_Tree.size();
  20.             Commend commend = stack_Tree.top().first;
  21.             int level = stack_Tree.top().second;
  22.             stack_Tree.pop();
  24.             if(commend.s == "print"){
  25.                 result.push_back(commend.node->val);
  26.             }
  27.             else{
  28.                 assert(commend.s == "go");
  29.                 if(commend.node->left){
  30.                     stack_Tree.push(make_pair(Commend("go",commend.node->left), level + 1));
  31.                 }
  32.                 if(commend.node->right){
  33.                     stack_Tree.push(make_pair(Commend("go",commend.node->right), level + 1));
  34.                 }
  35.                 if(record.find(level) == record.end()){
  36.                     record.insert(level);
  37.                     stack_Tree.push(make_pair(Commend("print",commend.node), level));
  38.                 }
  39.             }
  40.         }
  42.         return result;
  43.     }
  44. };

如果有错误或者不严谨的地方，请务必给予指正，十分感谢。