Count Good Nodes in Binary Tree - LeetCode
주어진 이진 트리에서 좋은 노드를 찾고, 좋은 노드의 개수를 반환하세요.
이 문제에서 좋은 노드는 다음과 같이 정의됩니다: 루트 노드부터 해당 노드까지의 경로 상에서 해당 노드의 값보다 큰 값을 가진 노드가 없는 노드입니다.
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 1:
Input: root = [3,1,4,3,null,1,5]
Output: 4
Explanation: Nodes in blue are good.
Root Node (3) is always a good node.
Node 4 -> (3,4) is the maximum value in the path starting from the root.
Node 5 -> (3,4,5) is the maximum value in the path
Node 3 -> (3,1,3) is the maximum value in the path.
Example 2:
Input: root = [3,3,null,4,2]
Output: 3
Explanation: Node 2 -> (3, 3, 2) is not good, because "3" is higher than it.
Example 3:
Input: root = [1]
Output: 1
Explanation: Root is considered as good.
문제 요약:
루트 노드부터 시작하여 각 노드를 검사하고, 해당 노드의 경로 상에서 더 큰 값을 가진 노드가 없으면 해당 노드는 좋은 노드로 간주합니다. 좋은 노드의 개수를 반환하세요.
풀이과정:
이 문제는 깊이 우선 탐색(DFS)을 사용하여 해결할 수 있습니다. 루트 노드에서 시작하여 각 노드를 검사하고 경로 상에서 더 큰 값을 가진 노드가 없으면 해당 노드는 좋은 노드로 간주합니다.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int goodNodes(TreeNode root) {
return getGoodNodeCnt(root, Integer.MIN_VALUE);
}
private int getGoodNodeCnt(TreeNode node, int maxValue){
int goodNodeCnt = 0;
if(node == null) return 0;
if(node.val >= maxValue){
goodNodeCnt++;
maxValue = node.val;
}
goodNodeCnt += getGoodNodeCnt(node.left, maxValue);
goodNodeCnt += getGoodNodeCnt(node.right, maxValue);
return goodNodeCnt;
}
}
1207. Unique Number of Occurrences (0) | 2023.10.29 |
---|---|
2215. Find the Difference of Two Arrays (0) | 2023.10.29 |
872. Leaf-Similar Trees (0) | 2023.10.26 |
104. Maximum Depth of Binary Tree (0) | 2023.10.26 |
394. Decode String (0) | 2023.10.26 |