1448. Count Good Nodes in Binary Tree

Description of Problem

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.

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.

Example 3:

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

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].

Solution

Tags: Binary Tree DFS

Explanation

When doing DFS, keep track the current maximum value of the path and the answer (count of good nodes).

Code

// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
// 
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
    pub fn good_nodes(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        let mut count = 0;
        Self::dfs(root, i32::MIN, &mut count);
        return count;
    }

    fn dfs(node : Option<Rc<RefCell<TreeNode>>>, max : i32, count : &mut i32){
        if let Some(n) = node {
            let n = n.borrow();
            if n.val >= max {
                *count += 1;
            }
            let max = max.max(n.val);
            Self::dfs(n.left.clone(), max, count);
            Self::dfs(n.right.clone(), max, count);
        }
    }
}

Complexity

n is the number of nodes in the tree
h is the height of the tree

Time complexity:

\( T(n) = \Theta(n) \)

Auxiliary Space:

\( S(n) = O(h) \)

Leetbook