1448. 统计二叉树中好节点的数目

难度: 中等

来源: 每日一题 2023.08.25

---

给你一棵根为 root 的二叉树，请你返回二叉树中好节点的数目。

「好节点」X 定义为：从根到该节点 X 所经过的节点中，没有任何节点的值大于 X 的值。

示例 1：

输入：root = [3,1,4,3,null,1,5]
输出：4
解释：图中蓝色节点为好节点。
根节点 (3) 永远是个好节点。
节点 4 -> (3,4) 是路径中的最大值。
节点 5 -> (3,4,5) 是路径中的最大值。
节点 3 -> (3,1,3) 是路径中的最大值。

示例 2：

输入：root = [3,3,null,4,2]
输出：3
解释：节点 2 -> (3, 3, 2) 不是好节点，因为 "3" 比它大。

示例 3：

输入：root = [1]
输出：1
解释：根节点是好节点。

提示：

• 二叉树中节点数目范围是 [1, 10^5] 。
• 每个节点权值的范围是 [-10^4, 10^4] 。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int goodNodes(TreeNode root) {

    }
}

分析与题解

---

• 深度优先遍历 + 前序遍历

  这个题目实际上就是对二叉树的深度优先遍历, 只不过我们需要携带当前链路的最大值作为参数. 每一次判断当前节点是否大于该值即可. 整体比较简单. 如果对前中后序遍历熟悉即可很快完成解题过程.

  最终的解题过程如下所示.

  /**
  * Definition for a binary tree node.
  * public class TreeNode {
  *     int val;
  *     TreeNode left;
  *     TreeNode right;
  *     TreeNode() {}
  *     TreeNode(int val) { this.val = val; }
  *     TreeNode(int val, TreeNode left, TreeNode right) {
  *         this.val = val;
  *         this.left = left;
  *         this.right = right;
  *     }
  * }
  */
  class Solution {
      // 前序遍历, 携带最大值
      public int goodNodes(TreeNode root) {
          return sortNode(root, root.val);
      }
  
      public int sortNode(TreeNode root, int maxValue) {
          if (root == null) {
              return 0;
          }
          int value = root.val;
          int count = 0;
          if (value >= maxValue) {
              count++;
              maxValue = value;
          }
          if (root.left != null) {
              count += sortNode(root.left, maxValue);
          }
          if (root.right != null) {
              count += sortNode(root.right, maxValue);
          }
          return count;
      }
  }
  

  
  

  复杂度分析:

  • 时间复杂度: O(n), 时间复杂度与 TreeNode 二叉树的个数相关.
  • 空间复杂度: O(n), 要构建与 TreeNode 二叉树的个数相关的空间.

  结果如下所示.