Leetcode 1448. Count Good Nodes in Binary Tree

태그
Algorithm
Leetcode
1448
공개여부
작성일자
2020/06/02

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.
find-good-nodes-1448-leetcode.png

정의

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 까지 검색해서 해봤으나 결과는…
find-good-nodes-1448-leetcode-2.png
와 진짜 너무 끔찍하다… 하긴 재귀호출마다 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;

결과

find-good-nodes-1448-leetcode-result.png
Runtime 이 1ms 이니 너무 기쁘다 ㅎ
잘푼거 같으니 discuss 에 올려야지
혹시 검색해서 오신분 계신다면 저의 풀이 좋아요좀 눌러주세요
Made with 💕 and Oopy