[LeetCode] 1448. Count Good Nodes in Binary Tree, Medium

1. 문제

• 이진 트리가 주어질 때, 자신까지 오는 경로 상에 자신보다 큰 값이 없었던 경우는 good 노드라 할 수 있다.
• 이진 트리 내에 존재하는 good 노드의 개수를 반환하라.

2. 해결

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function DFS(node: TreeNode | null, max : number) : number {
    if(!node) return 0;

    let count = 0;

    if(node.val >= max) {
        max = node.val;
        count++;
    }

    return count + DFS(node.left, max) + DFS(node.right, max);
}

function goodNodes(root: TreeNode | null): number {
    return DFS(root, Number.MIN_SAFE_INTEGER);
};

• DFS 탐색을하면서, 자신의 값이 max보다 큰 경우 count를 증가시키고 max를 갱신한다.
• left와 right 탐색의 결과 good 노드 개수와 합쳐 반환하면 된다.