[LeetCode 75/Binary Tree - BFS] 199 - Binary Tree Right Side View / 1161 - Maximum Level Sum of a Binary Tree (Java)

199 - Binary Tree Right Side View

---

풀이

이진 트리의 루트 노드가 주어졌을 때, 트리를 오른쪽에서 바라봄

-> 각 높이(level)마다 맨 오른쪽 노드만 보임

=> 각 레벨에서 마지막 노드 찾기

 

BFS로 트리를 레벨 순서로 탐색

ex. root = [1, 2, 3, , null, 5, null, 4]

• level 0 / [1] => 1
• level 1 / [2, 3] => 3
• level 2 / [5, 4] => 4

=> [1, 3, 4]

---

코드

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> arr = new ArrayList<>();
        if (root == null) return arr;

        Queue<TreeNode> q = new ArrayDeque<>();
        q.offer(root);
        
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = q.poll();

                if (i == size - 1) {
                    arr.add(node.val);
                }

                if (node.left != null) q.offer(node.left);
                if (node.right != null) q.offer(node.right);
            }
        }

        return arr;
    }
}

---

1161 - Maximum Level Sum of a Binary Tree

---

풀이

각 레벨 노드 값 합 계산해서 합이 가장 큰 레벨 번호 반환

-> `sum += node.val`

---

class Solution {
    public int maxLevelSum(TreeNode root) {
        Queue<TreeNode> q = new ArrayDeque<>();
        q.offer(root);

        int level = 1;
        int maxLevel = 1;
        int maxSum = Integer.MIN_VALUE;

        while (!q.isEmpty()) {
            int size = q.size();
            int sum = 0;

            for (int i = 0; i < size; i++) {
                TreeNode node = q.poll();
                sum += node.val;

                if (node.left != null) q.offer(node.left);
                if (node.right != null) q.offer(node.right);
            }

            if (sum > maxSum) {
                maxSum = sum;
                maxLevel = level;
            }

            level++;
        }

        return maxLevel;        
    }
}

코드

---

출처

LeetCode 75 - Study Plan - LeetCode