二叉树的右视图(BFS或DFS)

思路：

1.BFS，使用队列模拟BFS，层序遍历二叉树，从右子树开始遍历，每层第一个访问的就是最右边的那个结点。

2.DFS，使用栈模拟DFS，从右子树开始遍历，遍历到底。对树进行深度优先搜索，在搜索过程中，总是先访问右子树。那么对于每一层来说，我们在这层见到的第一个结点一定是最右边的结点。

3.都需要知道当前结点在哪一层，所以要用map记录。可以存储在每个深度访问的第一个结点，一旦我们知道了树的层数，就可以得到最终的结果数组。

//BFS /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vector<int> rightSideView(TreeNode* root) { if(root==nullptr) return {}; unordered_map<int,int> num; queue<pair<TreeNode*,int>> node_depth; node_depth.push({root,0}); int maxdep=-1; while(!node_depth.empty()){ auto p=node_depth.front(); node_depth.pop(); TreeNode* nod=p.first; int dep=p.second; if(nod!=nullptr){ maxdep=max(maxdep,dep); if(num.find(dep) == num.end()){ num[dep]=nod->val; } node_depth.push({nod->right,dep+1}); node_depth.push({nod->left,dep+1}); } } vector<int> rightsort; for(int i=0;i<=maxdep;i++){ rightsort.push_back(num[i]); } return rightsort; } }; //DFS class Solution { public: vector<int> rightSideView(TreeNode* root) { if(root==nullptr) return {}; unordered_map<int,int> num; stack<pair<TreeNode*,int>> node_depth; node_depth.push({root,0}); int maxdep=-1; while(!node_depth.empty()){ auto p=node_depth.top(); node_depth.pop(); TreeNode* nod=p.first; int dep=p.second; if(nod!=nullptr){ maxdep=max(maxdep,dep); if(num.find(dep) == num.end()){ num[dep]=nod->val; } node_depth.push({nod->left,dep+1}); node_depth.push({nod->right,dep+1}); } } vector<int> rightsort; for(int i=0;i<=maxdep;i++){ rightsort.push_back(num[i]); } return rightsort; } };