cleanUrl: /posts/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.

https://blog.yevgnenll.me/media/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 까지 검색해서 해봤으나 결과는…

https://blog.yevgnenll.me/media/find-good-nodes-1448-leetcode-2.png

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