기억하고싶은것들

There are n rooms labeled from 0 to n - 1 and you start in the room 0.

All the rooms labeled from 1 to n are initially locked and you cannot enter a locked room without having its key.

When you visit a room, you may find a set of distinct keys in it

and you can use them to open locked rooms and enter them.

You can visit the same room any number of times and the goal is to visit all the nrooms.

Given an array rooms where rooms [i] is the set of keys that you can obtain if you visited room i,

return true if you can visit all the rooms, or falseotherwise.

0부터 n-1까지의 이름 지어진 방이 있고, 0번째 방부터 시작된다.

1부터 n까지의 모든 방은 초반에 잠겨 있고, 열쇠가 없이는 들어갈 수 없다.

특정 방에 방문했을 때, 열쇠 꾸러미를 발견할 수 있고 그 열쇠 꾸러미를 이용해 잠긴 방을 방문할 수 있다.

방문했던 방에는 몇 번이고 중복해서 방문할 수 있고, 최종 목표는 모든 방에 방문하는 것이다.

방들의 배열이 주어지고, 해당 방에는 열쇠 꾸러미 정보를 가지고 있다.

만약 주어진 정보로 모든 방들을 방문할 수 있으면 true를 반환하고 그렇지 않으면 false를 반환하라.

주어진 방들과 열쇠들의 정보는 tree 형태로 형상화할 수 있다.

주어진 트리를 방문하며, 방문한 방들의 정보를 저장하고 모든 트리의 노드를 순회했을 때 저장한 방문한 방들의 모든 정보가 주어진 방들의 길이와 같으면 모든 방을 방문한 것이다.

recursive 한 형태로 순환을 하고, Depth First Search를 이용하여 tree를 방문하여 보자.

    public boolean canVisitAllRooms(List<List<Integer>> rooms) {

        List<Integer> visited = new ArrayList<>(); // 방문한 방들의 정보를 저장

        recursiveVisit(visited, rooms, 0); // 0번 방부터 시작

        if (visited.size() == rooms.size()) { // 주어진 방의 갯수와 방문한 방의 갯수 비교 
            return true;
        }
        return false;
    }

    private void recursiveVisit(List<Integer> visited, List<List<Integer>> rooms, int i) {

        visited.add(i);
        List<Integer> list = rooms.get(i);

        for (int idx : list) {
            if (!visited.contains(idx)) { // 이미 방문한 방은 다시 방문할 필요가 없다
                recursiveVisit(visited, rooms, idx);
            }
        }
    }

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/

Given the root of a binary tree, return the sum of values of its deepest leaves.

binary tree의 root 값이 주어진 상황에서, 가장 끝에 있는 잎들의 합을 반환해라.

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

dfs를 타고 갈 때마다 level의 값을 하나씩 더해주어 해당 노드의 level을 파악하고

해당 level이 maxLevel보다 큰 경우에는 maxLevel값으로 세팅해 주면서 해결해 나갈 수 있을 것으로 보인다. 

    private void dfs(TreeNode node, int level) {

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

        if (level == maxLevel) {
            sum += node.val;
        }

        if (node.right != null) {
            dfs(node.right, level+1);            
        }

        if (node.left != null) {
            dfs(node.left, level+1);
        }
    }

해당 메서드를 호출하는 내역을 보자

sum, maxLevel은 전역 변수를 사용하였다.

    int sum = 0;
    int maxLevel = 0;

    public int deepestLeavesSum(TreeNode root) {
        int level = 0;

        if (root != null) {
            dfs (root, level);
        }

        return sum;    
    }

문제 출처 

leetcode.com/problems/deepest-leaves-sum/