[Grind75-LeetCode] Binary Tree Right Side View JAVA

반응형

728x90

[Grind75-LeetCode] Binary Tree Right Side View - Medium 

---

접근

• dfs

---

풀이

이진트리를 오른쪽에서 바라봤을 때 보이는 노드들을 루트에서 바닥까지의 순서로 반환하는 문제이다. 즉 트리의 제일 오른쪽 노드들을 순서대로 반환하면 된다. 각 레벨의 노드를 오른쪽에서 봤을 때 제일 먼저 만나는 노드를 반환하는 문제이기 때문에 오른쪽 서브트리의 노드만 해당하는 것이 아니라 해당 레벨에 맨 왼쪽 노드 하나만 존재한다면 해당 노드가 반환할 목표 노드가 된다. 

    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        dfs(result, root, 0);

        return result;
    }

결과 리스트와 트리의 루트, 그리고 레벨을 파라미터로 dfs를 실행한다.

    private void dfs(List<Integer> res, TreeNode node, int level) {
        if (node == null) {
            return;
        }

        if (level == res.size()) {
            res.add(node.val);
        }

        dfs(res, node.right, level + 1);
        
        dfs(res, node.left, level + 1);
    }

푸는 법은 간단하다. 오른쪽 서브트리부터 탐색을 진행해 해당 레벨의 제일 오른쪽 노드가 추가되지 않은 상태라면 추가하면 된다. 만약 레벨 2의 노드가 2개가 있고 레벨 3의 제일 오른쪽 노드를 찾아야 할 때 레벨 2의 오른쪽 노드의 오른쪽 서브트리부터 접근을 하게 된다. 만약 오른쪽 노드의 오른쪽 서브트리가 존재한다면 해당 노드가 레벨 3의 반환값이 되고 존재하지 않는다면 왼쪽 서브트리에 접근하고 또 존재하지 않는다면 레벨 2 왼쪽 노드의 오른쪽 서브트리에 접근하는 방법으로 노드가 존재할 때까지 진행한다. 코드 상에선 노드가 존재하지 않는 경우 해당 서브트리 탐색을 종료하고 노드가 존재하는데 만약 현재 레벨과 결과 리스트의 크기가 같다면 현재 노드가 해당 레벨의 제일 오른쪽 노드가 되므로 리스트에 추가하게 된다. 그리고 이어서 다음 레벨을 진행한다.

---

전체 코드

/**
 * 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) {
        List<Integer> result = new ArrayList<>();
        dfs(result, root, 0);

        return result;
    }

    private void dfs(List<Integer> res, TreeNode node, int level) {
        if (node == null) {
            return;
        }

        if (level == res.size()) {
            res.add(node.val);
        }

        dfs(res, node.right, level + 1);
        
        dfs(res, node.left, level + 1);
    }
}