기억하고싶은것들

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 the root of a binary tree, find the maximum value V for which there exist different nodes A and B where V = |A.val - B.val| and A is an ancestor of B.

A node A is an ancestor of B if either: any child of A is equal to B, or any child of A is an ancestor of B.

이진트리의 루트가 주어진다. V의 최댓값을 구해라 

A가 B의 조상인 경우에 V = |A.val - B.val| 

A가 B의 조상이라고 말하는 경우는 아래와 같다

A의 어떠한 자식이 B와 같은 경우 거나, A의 어떠한 자식이든 B의 선조인 경우이다. 

( 쉽게 말해, 이진트리에 존재하는 노드의 값들 중 노드의 값의 차가 최댓값인 것을 구해라 ) 

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

노드를 방문하며, 지금까지 구한 min, max값을 파라미터로 넘기고 

현재 방문한 노드의 값이 min, max값에 해당하는지 비교하여 값을 업데이트 한 후에 

min과 max의 차를 result로 저장하면 된다.

    private void dfs(TreeNode node, int min, int max) {
        min = Math.min(node.val, min);
        max = Math.max(node.val, max);

        rst = Math.max(rst, max -min);

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

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

해당 메소드를 호출하는 부분을 보자.

결과 값은 전역변수로 선언하였다.

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

전역 변수를 사용하지 않는 경우에는 result가 되는 값을 파라미터로 넘기면 된다.

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

    private int dfs(TreeNode node, int max, int min, int rst) {

        min = Math.min(node.val, min);
        max = Math.max(node.val, max);

        rst = Math.max(rst, max -min);
        int right = rst;
        if (node.right != null) {
            right = dfs(node.right, max, min,rst);
        }

        int left = rst;
        if (node.left != null) {
            left = dfs (node.left, max, min, rst);
        }

        return Math.max(left, right);
    }

문제 출처

leetcode.com/problems/maximum-difference-between-node-and-ancestor/

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/

Given the root of a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus sum of all keys greater than the original key in BST.

As a reminder, a binary search tree is a tree that satisfies these constraints:

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• Both the left and right subtrees must also be binary search trees.

BST의 root 노드가 주어지고, 이 노드를 Greater Tree로 변환하여라.

BST의 모든 key값은 -> 초기값 + 해당 노드보다 큰 key값을 가진 노드의 합으로 변경된다. 

아래는 BST가 만족하는 제약사항들이다.

• 왼쪽 하위 트리는 해당 노드의 key값보다 작은 노드들로만 구성된다.
• 오른쪽 하위 트리는 해당 노드의 key값보다 큰 노드들로만 구성된다.
• 오른쪽, 왼쪽의 모든 하위 트리는 BST이다. 

DFS를 이용해서 해당 문제의 답을 구해보자.

자기 자신보다 큰 값을 가지고 있는 노드들의 합을 구해야 하므로 가장 큰 값을 가지고 있는 노드부터 자기 자신의 값을 더해가면서 그 합들을 구해가면 된다. 

BST의 특성상 가장 큰 값은 트리의 오른쪽 노드들만 타고 가면 나오고

가장 끝의 도달한 순간 부터는 해당 노드의 value를 total sum과 더해가면서 노드의 value값을 변환하면 된다. 

    private void dfs(TreeNode node) {
        if (node.right != null) {
            dfs (node.right);
        }
        int temp = node.val;
        node.val = sum + temp;
        sum = node.val;

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

오른쪽 subTree를 모두 순회한 후에 왼쪽 서브 트리를 같은 방식으로 순회하면 된다.

(왼쪽의 subTree의 경우에도 가장 큰 값은 오른쪽 끝에 존재) 

이제 해당 메서드를 호출하는 메서드를 보자.

누적 sum을 나타내는 값은 전역변수로 선언하였다.

    int sum = 0;
    public TreeNode bstToGst1(TreeNode root) {
        
        if (root != null) {
            dfs(root);
        }

        return root;
    }

문제 출처

leetcode.com/problems/binary-search-tree-to-greater-sum-tree/