기억하고싶은것들

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/

Given a binary tree root, a node X in the tree is named good if in the path from root to X there are no nodes with a value greater than X.

Return the number of good nodes in the binary tree.

이진트리의 루트가 주어진다,  

트리에서 루트부터 X까지의 길에서 X보다 큰 값을 가진 노드가 없는 경우, 노드 X는 좋은 노드이다.

이진트리에서 좋은 노드의 개수를 반환해라.

dfs를 이용하서 해답을 구해보자.

이진트리 노드를 탐색하며, 자신이 지나간 길에 max value를 저장하고 방문한 노드의 값이 max value보다 같거나 크면 

좋은 노드의 조건에 만족할 수 있다. 

    private void dfs(TreeNode node, int val) {

        val = Math.max(val, node.val);
        if (node.val >= val) {
            rst++;
        }

        if (node.right != null) {
            dfs(node.right, val);
        }

        if (node.left != null) {
            dfs(node.left, val);
        }
    }

해당 메서드를 호출하는 메서드의 코드를 보자.

총 좋은 노드의 갯수를 나타내는 변수는 전역 변수로 선언하였다. 

    int rst = 0;
    public int goodNodes(TreeNode root) {
        if (root != null) {
            dfs(root, root.val);
        }
        return rst;
    }

문제 출처 :

leetcode.com/problems/count-good-nodes-in-binary-tree/