199. 二叉树的右视图

难度

中等

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

示例:

输入: [1,2,3,null,5,null,4]
输出: [1, 3, 4]
解释:

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

https://leetcode-cn.com/problems/binary-tree-right-side-view/

深度优先递归【DFS+记忆存储】

纯手打记录自己解题思路：

• 通过深度遍历获取每一行的最右侧节点，这里需要体现两点：1、每一行 2、最右侧。
• 如何体现每一行：通过记录深度来达到对行的体现
• 如何体现最右侧：通过建立 Map 来记录每一行中的元素，通过对当前树逆后序遍历【自己的定义方式：就遍历根节点后遍历右子树直到叶子节点，再遍历左子树直到叶子节点】遍历到的当前行记录第一个add 到 map 的元素即为右侧看到的第一个元素。

整体的思路还是比较简单的，追根到底还是递归，只不过用了 map 来临时存储，代码如下：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
//  构建 key 为深度，node_value 为值的 map 的全局变量
    private HashMap<Integer,Integer>  map = new HashMap();
    public List<Integer> rightSideView(TreeNode root) {
        // 初始化深度为0
        helper(root,0);
        // 通过 map_value 构造 List
        return new ArrayList(map.values());
    }

    private void helper(TreeNode root,Integer depth){
        if(root != null) {
            depth++;
            // 判断当前层是否有元素，由于是【逆后序遍历】，如果key存在则已有当前层最右侧节点了，否则将最右侧节点value添加进去，然后再次对此节点的右子树和左子树递归
            if(!map.containsKey(depth)) map.put(depth, root.val);
            if(root.right != null) helper(root.right, depth);
            if(root.left != null) helper(root.left, depth);
        }

    }
}