기억하고싶은것들

Given the root of a binary tree, return an array of the largest value in each row of the tree (0-indexed).

이진트리의 루트가 주어지고, 트리의 각 레벨의 가장 큰 값들을 담은 배열을 반환해라. ( 0부터 시작 )

해당 문제에서는 트리의 레벨 별로 특정한 값을 찾는 문제 이므로, 트리의 레벨별로 그래프를 순환하는 bfs를 사용하여 문제를 해결해 보자.

    public List<Integer> largestValues(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<Integer> rst = new ArrayList<>();
        if (root == null) { // Check Input is Null
            return rst;
        }
        
        queue.add(root); 
        while (!queue.isEmpty()) { // Check by Tree Level
            int size = queue.size();
            int max = Integer.MIN_VALUE;

            for (int i = 0; i < size; i++) { // Only Rotate Level Node 
                TreeNode temp = queue.poll();
                if (temp.val > max) {
                    max = temp.val;
                }

                if (temp.right != null) {
                    queue.add(temp.right);
                }
                if (temp.left != null) {
                    queue.add(temp.left);
                }
            }
            rst.add(max);
        }
        return rst;
    }

Given the root of a binary tree, return the leftmost value in the last row of the tree.

이진트리의 루트가 주어지고, 트리의 가장 밑에 왼쪽 값을 리턴해라.

이 문제에서는 특정한 레벨의 값을 찾는 문제이므로, 레벨별로 트리를 탐색하는 bfs 알고리즘을 사용하는 것이 좋을 것이다. 또한 가장 왼쪽의 값이라면, bfs에서 트리를 탐색할 때 방문한 노드의 왼쪽 값부터 queue에 넣는다면 방문한 레벨의 첫 번째 값이 가장 왼쪽에 존재하는 값이 될 것이다.

    public int findBottomLeftValue(TreeNode root) {

        Queue<TreeNode> queue = new LinkedList<>();

        if (root == null) {
            return 0;
        }
        queue.add(root);

        int rst = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();

            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (i == 0) {
                    rst = node.val;
                }

                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
        }
        return rst;
    }

문제 출처 : 

leetcode.com/problems/find-bottom-left-tree-value/

Given an n-ary tree, return the level order traversal of its nodes' values.

Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value (See examples).

n-ary 트리가 주어지고, 노드의 값을 포함한 레벨 순서의 순회 결과를 반환해라 

Nary-Tree 입력값은 레벨 순서 순회로 표시됩니다.

각 그룹의 자식들은 null값으로 구분 지어집니다.

문제의 포인트는 결과적으로 주어진 트리의 레벨 별로 배열을 만들어 해당 배열이 포함된 결과를 반환하면 된다.

즉, 레벨 별로 어떠한 노드가 존재하는지 파악하기 위해서는 bfs를 사용하는 것이 적합하다.

    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> rst = new ArrayList<>();

        if (root == null) {
            return rst;
        }

        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            List<Integer> list = new ArrayList<>();
            int size = queue.size();

            for (int i = 0; i < size; i++) {
                Node node = queue.poll();
                list.add(node.val);

                if (node.children != null) {
                    for (Node n : node.children) {
                        queue.add(n);
                    }
                }
            }
            rst.add(list);
        }
        return rst;
    }

문제 출처 :

leetcode.com/problems/n-ary-tree-level-order-traversal/

Given the root of a binary tree, the level of its root is 1, the level of its children is 2, and so on.
Return the smallest level x such that the sum of all the values of nodes at level x is maximal.

이진트리의 루트가 주어지고, 루트의 레벨은 1이고, 루트의 자식의 레벨은 2이고 그 하위도 레벨이 1식 증가한다.

동일 레벨의 값 합이 가장 큰 레벨을 리턴하라, 단 가장 작은 레벨을 리턴하라. 

트리의 레벨별로 값의 합을 구하면 되므로 bfs를 이용하여 해답을 구해보자.

bfs는 Queue 자료구조를 사용하여 구현가능하다.

    public int maxLevelSum(TreeNode root) {
        
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        int level = 0;
        int minLevel = 0, maxSum = Integer.MIN_VALUE;
        while (!queue.isEmpty()) {
            int size = queue.size();
            level++;
            int levelSum = 0;
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                levelSum += node.val;
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);

            }
            if (levelSum > maxSum) {
                maxSum = levelSum;
                minLevel = level;
            }
        }
        return minLevel;
    }

문제 출처 : 

leetcode.com/problems/maximum-level-sum-of-a-binary-tree/