LeetCode-1148 Count Good Nodes in Binary Tree [Java]

풀어보다가 굉장히 좋은 문제라고 생각하여 글을 쓴다.

문제

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이다
• 예) 리프노드인 5 는 Good Node이다. 3-4-5 의 경로가 해당 조건을 만족하기 때문이다.

접근

1. 한개의 노드를 탐색한다.
2. 루트노드부터 직전의 노드의 경로에 존재하는 최대값보다 현재의 노드의 값이 크거나 같으면 → Good Node이다.

→ 재귀를 타면서 최대값을 계속 갱신해서 내려줘야한다.

코드

    static int dfs(TreeNode node, int maxValue){
        if(node==null) return 0;

        int count =0; //현재 탐색중인 서브 트리의 Good node의 개수
        
        if(node.val>=maxValue) count+=1; // 접근 2.
        
        int nextMaxValue = Math.max(maxValue,node.val);//최대값을 갱신
        
        count+= dfs(node.left,nextMaxValue); //현재 탐색중인 서브트리의, 왼쪽 서브트리에게 값을 전달
        count+= dfs(node.right,nextMaxValue); // 현재 탐색중인 서브트리의, 오른쪽 서브트리에게 값을 전달
        
        return count;
    }