Count Good Nodes in Binary Tree

문제

https://leetcode.com/problems/count-good-nodes-in-binary-tree/description/

LeetCode - The World's Leading Online Programming Learning Platform

풀이 코드

• DFS로 Tree를 순회한다.
• 각 Node의 값이 순회 경로 상에 있는 Node들의 최댓값보다 크면 최댓값을 변경하고 answer를 1 증가한다.
• Tree를 모두 순회하면 answer를 return한다.

/**
 * 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 {

    int answer; //good node의 개수를 담을 변수

    public int goodNodes(TreeNode root) {
        answer = 0; //0으로 초기화
        DFS(root, root.val); //root는 항상 good node 이므로, 첫 max값으로 root node의 값을 넣는다.
        return answer;
    }

    private void DFS(TreeNode node, int max) {
        if (node == null) {
            return;
        } else {
            if (node.val >= max) {
                max = node.val;
                answer++;
            }
            DFS(node.left, max);
            DFS(node.right, max);
        }
    }
}