The problem

Count Good Nodes in Binary Tree Medium

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.
Copy the code

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.
Copy the code

Example 3:

Input: root = [1]
Output: 1
Explanation: Root is considered as good.
Copy the code

Constraints:

  • The number of nodes in the binary tree is in the range [1, 10 ^ 5).
  • Each node’s value is between [- 10 ^ 4, 10 ^ 4).

Their thinking

To determine whether the current node is a good node, we only need to know all the ancestor nodes of the node, which have nothing to do with its siblings. Therefore, we can use DFS depth-first search to traverse the entire tree.

When we judge a node, if its parent is a good node, then it is a good node as long as it is greater than or equal to its parent. If the parent node is not a good node, then find the nearest good ancestor node and compare it. Because the comparison is one-way, we can easily find the closest good ancestor node for comparison by recording the last good node (or the value of the good node) during DFS.

Refer to the answer

public class Solution {
    int cnt;
    
    public int goodNodes(TreeNode root) {
        cnt = 0;
        // search from root
        DFS(root, null);
        return cnt;
    }

    void DFS(TreeNode node, TreeNode lastGoodNode) {
        // current node is good or not
        boolean isGood = false;
        // lastGoodNode == null means current node is root and need to be counted
        // when it's not root and node.val >= lastGoodNode.val then count
        if (lastGoodNode == null || node.val >= lastGoodNode.val) {
            cnt++;
            isGood = true;
        }
        
        if(node.left ! =null) {
            DFS(node.left, isGood ? node : lastGoodNode);
        }
        if(node.right ! =null) { DFS(node.right, isGood ? node : lastGoodNode); }}}Copy the code

Expand training

Try the same DFS problem!

[LeetCode] [Hard] Making A Large Island’s largest artificial Island | Java

Or check out the author’s LeetCode column for additional questions of interest!

Juejin. Cn/column / 6997…

The data link

The original leetcode.com/problems/co…

Depth-first search zh.wikipedia.org/wiki/%E6%B7…