[LeetCode] - M - 199. Binary Tree Right Side View

https://leetcode.com/problems/binary-tree-right-side-view/description/?envType=study-plan-v2&envId=top-interview-150

Binary Tree Right Side View - LeetCode

 

🌿 - 문제 설명

Given the root of a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

간단하게 설명하면 tree의 depth에서 가장 오른쪽 값을 반환

 

📌 - 풀이

처음엔 rightNode들만 반환하면 되는 줄 알았는데, 각각의 depth에서 가장 오른쪽 노드를 찾는 문제였음

1. 중위순회를 한다.
2. 중위순회를 하면 왼쪽에서 오른쪽으로 진행하기 때문에, map을 이용해서 map의 키값을 depth로 놓으면 해당 depth에서 가장 오른쪽 노드만 계속해서 덮여쓰기 되므로 원하는 값을 찾을 수 있음

 

🔥 - Java 코드

 

/**
 * 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 {
    List<Integer> list = new ArrayList<>();
    Map<Integer,Integer> map = new HashMap<>();
    public List<Integer> rightSideView(TreeNode root) {

        inorder(root,1);
        for(int a : map.keySet()){
            list.add(map.get(a));
        }
        return list;
    }

    public void inorder(TreeNode node,int depth){
        if(node == null){
            return;
        }

        inorder(node.left,depth +1);
        map.put(depth,node.val);
        inorder(node.right,depth +1);
    }
}