LeetCode 199 - Binary Tree Right Side View

Binary Tree Right Side View - LeetCode

 

이진트리의 root가 주어졌을 때 자신의 우측 방향에서 바라봤을 때 보이는 노드들의 값을 위에서 아래방향으로 반환하라.

오른쪽에서 봤을 때라는 뜻은 각 레벨마다 오른쪽에 있는 값이라는 뜻이다.

그렇다면 레벨별로 탐색하는 것이 중요하다.

레벨별로 탐색은 어떻게 가능할까? BFS를 사용하면 된다.

다음의 작업을 처리하면 된다.

1. 현재 레벨의 처리해야 할 노드 수를 기록한다.
2. 해당 레벨의 모든 노드를 순회한다.
3. 그 노드의 왼쪽, 오른쪽 자식이 있다면 큐에 추가한다.
4. 해당 레벨의 마지막 노드이면 결과 리스트에 추가한다.

/**
 * 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<>();
        if (root == null) return result;
        
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);

        while (!q.isEmpty()) {
            int levelSize = q.size();
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = q.poll();
                if (i == levelSize - 1) {
                    result.add(node.val);
                }
                if (node.left != null) q.add(node.left);
                if (node.right != null) q.add(node.right);
            }

        }
        return result;
    }    
}

 

그런데 이 문제는 DFS로도 해결이 가능하다.

트리를 탐색해 나가면서 오른쪽 자식을 먼저 보면 당연히 오른쪽에서 바라보는 노드의 값을 얻을 수 있다.

문제는 이제 왼쪽 서브트리에서 레벨이 더 큰 자식이 나왔을 때이다.

이를 해결하기 위해 레벨과 찾은 오른쪽에서 바라봤을 때의 노드 개수를 연관 지어 처리해 줄 방법이 필요하다.

해당 레벨에는 하나의 정답 노드가 존재할 것이다. 따라서 저장된 노드의 개수와 레벨을 비교하면 된다.

/**
 * 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<>();
        if (root == null) return result;
        dfs(0, root, result);
        return result;
    }    

    private void dfs(int level, TreeNode node, List<Integer> result) {
        if (node == null) return;
        
        if (level == result.size()) {
            result.add(node.val);
        }

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