All Articles

Leetcode 1448. Count Good Nodes in Binary Tree

1448. Count Good Nodes in Binary Tree

Good node 의 갯수를 세어보자

문제가 재밋네유

문제

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.

example leetcode Count Good Nodes in Binary Tree

정의

Good node 라 함은 root 에서 노드 X 까지 가는데 노드 X 보다 큰 값이 없다면 good node 인데

중요한 점은 root 는 무조건 good node 이다.

내 풀이

class Solution {
    public int goodNodes(TreeNode root) {
        return isGood(root, new ArrayList<>());
    }
    private int isGood(TreeNode node, List<Integer> list) {
        if (node == null) return 0;
        list.add(node.val);
        int sum = 0;
        if (Collections.max(list) == node.val) {
            sum += 1;
        }
        if (node.left != null) {
            sum += isGood(node.left, new ArrayList<>(list));
        }
        if (node.right != null) {
            sum += isGood(node.right, new ArrayList<>(list));
        }
        return sum;
    }
}

일단 푸는데 급했다.. ㅠㅠ 먼저 root 에서 대상 노드 X 까지 가는 값을 모두 list 에 저장해서

가장 큰 값을 찾고, 가장 큰 값이 현재 node 의 값과 비교했을때 같거나 작다면 good node 에 해당한다고 생각했다.

그래서

List<Integer> list = new ArrayList<>();
Collections.max(list);

라는 collection API 까지 검색해서 해봤으나 결과는…

accepted but bad result

와 진짜 너무 끔찍하다… 하긴 재귀호출마다 list 를 새로 생성하는데 심각한 수준의 공간사용에 이런 결과는 당연한 것이다.

그렇다면 어떻게 list 를 사용하지 않고 문제를 해결할 수 있을까??

맨 처음에 생각했던건 StringBuffer 였다.

list나 array 와 같은 역할을 하게끔 만들어야겠다 라는 생각이 압도적이었기 때문이다.

그런데 node 안에 값의 type 은 int 니까 계산을 하는게 훨씬 좋지 않을까?? (매우 당연)

class Solution {
    public int goodNodes(TreeNode root) {
        return isGood(root, root.val);
    }
    private int isGood(TreeNode node, int max) {
        if (node == null) return 0;
        int sum = node.val >= max ? 1 : 0;
        if (node.left != null) {
            sum += isGood(node.left, Math.max(max, node.val));
        }
        if (node.right != null) {
            sum += isGood(node.right, Math.max(max, node.val));
        }
        return sum;
    }
}

알고리즘을 풀다보면 이런 생각을 당연히 해야하는데..

이전 값 까지의 최대값과 현재값 두 int 의 최대값을 한다면 그 중에서 가장 최대값을 유지하며 비교할 수 있지 않겠는가

int sum = node.val >= max ? 1 : 0;

결과

accepted and optimal

Runtime 이 1ms 이니 너무 기쁘다 ㅎ

잘푼거 같으니 discuss 에 올려야지

혹시 검색해서 오신분 계신다면 저의 풀이 좋아요좀 눌러주세요