[Leetcode][Java]1448 Count Good Nodes in Binary Tree ( 이진트리의 Good 노드 갯수 )

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.

 

이진트리의 루트가 주어진다,  

트리에서 루트부터 X까지의 길에서 X보다 큰 값을 가진 노드가 없는 경우, 노드 X는 좋은 노드이다.

이진트리에서 좋은 노드의 개수를 반환해라.

---

dfs를 이용하서 해답을 구해보자.

이진트리 노드를 탐색하며, 자신이 지나간 길에 max value를 저장하고 방문한 노드의 값이 max value보다 같거나 크면 

좋은 노드의 조건에 만족할 수 있다. 

    private void dfs(TreeNode node, int val) {

        val = Math.max(val, node.val);
        if (node.val >= val) {
            rst++;
        }

        if (node.right != null) {
            dfs(node.right, val);
        }

        if (node.left != null) {
            dfs(node.left, val);
        }
    }

해당 메서드를 호출하는 메서드의 코드를 보자.

총 좋은 노드의 갯수를 나타내는 변수는 전역 변수로 선언하였다. 

    int rst = 0;
    public int goodNodes(TreeNode root) {
        if (root != null) {
            dfs(root, root.val);
        }
        return rst;
    }

 

문제 출처 :

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

Count Good Nodes in Binary Tree - LeetCode