1448.Count-Good-Nodes-in-Binary-Tree.md

1448. Count Good Nodes in Binary Tree

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 aregood.
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 asgood.

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

Note

---

Code

---

• GoLang

  Runtime 75ms Beats 73.84% of users with Go

  Memory 13.01MB Beats **8.72%**of users with Go

  /**
   * Definition for a binary tree node.
   * type TreeNode struct {
   *     Val int
   *     Left *TreeNode
   *     Right *TreeNode
   * }
   */
  func goodNodes(root *TreeNode) int {
      if root == nil {
          return 0
      }
  
      count := 0
      var countGoodNode func(node *TreeNode, max int)
      countGoodNode = func(node *TreeNode, max int) {
          if node == nil {
              return
          }
  
          if node.Val >= max {
              max = node.Val
              count++
          }
  
          countGoodNode(node.Left, max)
          countGoodNode(node.Right, max)
      }
  
      countGoodNode(root, root.Val)
  
      return count
  }

• PHP

  Runtime 74ms Beats 56.52% of users with PHP

  Memory 31.82MB Beats 86.96% of users with PHP

  /**
   * Definition for a binary tree node.
   * class TreeNode {
   *     public $val = null;
   *     public $left = null;
   *     public $right = null;
   *     function __construct($val = 0, $left = null, $right = null) {
   *         $this->val = $val;
   *         $this->left = $left;
   *         $this->right = $right;
   *     }
   * }
   */
  class Solution {
  
      /**
       * @param TreeNode $root
       * @return Integer
       */
      function goodNodes($root) {
          if (is_null($root)) {
              return 0;
          }
  
          return $this->getGoodNodeCount($root, $root->val, 0);
      }
  
      private function getGoodNodeCount($node, int $max, int $count): int {
          if (is_null($node)) {
              return $count;
          }
  
          if ($node->val >= $max) {
              $count++;
              $max = $node->val;
          }
  
          $count = $this->getGoodNodeCount($node->left, $max, $count);
          $count = $this->getGoodNodeCount($node->right, $max, $count);
  
          return $count;
      }
  }

Reference

---