199.二叉树的右视图（两种方法实现）

一、题目

思路1

对于一个任意给定的二叉树，我们不能确定二叉树的形状；

设计一个每次遍历二叉树的右子树的深度优先遍历，这样深度优先遍历中每层遍历到的第一个结点就是最右边的结点；

代码实现大致分为四部分：

哈希表存储当前层对应的第一个遍历到的结点
结点栈实现每次遍历二叉树的右子树的深度优先遍历
深度栈保存结点栈的每个结点对应的深度
哈希表中不存在以当前层次为键的值，说明是深度优先遍历的第一个结点（最右结点）

思路1代码实现

/*** 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) {unordered_map<int, int> rightmostValueAtDepth;int max_depth = -1;stack<TreeNode*> nodeStack;stack<int> depthStack;nodeStack.push(root);depthStack.push(0);while(!nodeStack.empty()) {TreeNode* node = nodeStack.top(); nodeStack.pop();int depth = depthStack.top(); depthStack.pop();if(node) {max_depth = max(max_depth, depth);if(rightmostValueAtDepth.find(depth) == rightmostValueAtDepth.end()){//如果调用find方法没发现当前depth对应的数字 返回rightmostValueAtDepth.end()rightmostValueAtDepth[depth] = node -> val;}nodeStack.push(node -> left);nodeStack.push(node -> right);depthStack.push(depth + 1);depthStack.push(depth + 1);}}vector<int> rightView;for(int depth = 0; depth <= max_depth; depth ++)rightView.push_back(rightmostValueAtDepth[depth]);return rightView;}
};

思路二

二叉树的右视图，我们可以利用队列的先入先出，后入后出的结构特点实现广度优先搜索，对二叉树进行层序遍历，每一层的最后访问的结点就是右视图能看到的结点。

代码实现大致分为四步

哈希表存储当前节点所在层次和对应的值
创建节点队列，实现对节点的广度优先遍历
层次队列保存对应节点的所在层数
不断更新哈希表的二叉树的每一层对应的结点值，实现存储每一次层序遍历的最后一个结点

思路二代码实现

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public List<Integer> rightSideView(TreeNode root) {Map<Integer, Integer> rightmostValueAtDepth = new HashMap<Integer, Integer>();int max_depth = -1;Queue<TreeNode> nodeQueue = new LinkedList<TreeNode>();Queue<Integer> depthQueue = new LinkedList<Integer>();nodeQueue.add(root);depthQueue.add(0);while(!nodeQueue.isEmpty()) {TreeNode node = nodeQueue.remove();int depth = depthQueue.remove();if(node != null) {max_depth = Math.max(max_depth, depth);//由于每一层最后一个结点才是想要的答案 因此不断更新哈希表中深度对应的节点值即可rightmostValueAtDepth.put(depth, node.val);nodeQueue.add(node.left);nodeQueue.add(node.right);depthQueue.add(depth + 1);depthQueue.add(depth + 1);}}List<Integer> rightView = new ArrayList<Integer>();for(int depth = 0; depth <= max_depth; depth ++)rightView.add(rightmostValueAtDepth.get(depth));return rightView;}}