LeetCode 每日一题
java数据结构与算法深度优先遍历

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);
        }

    }
}
暂无评论