一、题目
思路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;}}
