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.
정의
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 까지 검색해서 해봤으나 결과는…
와 진짜 너무 끔찍하다… 하긴 재귀호출마다 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;
결과
Runtime 이 1ms 이니 너무 기쁘다 ㅎ
잘푼거 같으니 discuss 에 올려야지
