web购物网站模板下载12345微信公众号

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

题目描述

思路

对二叉树进行先序遍历，边遍历边对比并更新当前路径上的最大值pathMax，若当pathMax小于等于当前节点值，则好节点的数目加一

复杂度

时间复杂度:

$O(n)$;其中$n$为二叉树的节点个数

空间复杂度:

$O(h)$；其中$h$为二叉树的高度

Code

/*** 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 {int count = 0;public int goodNodes(TreeNode root) {traverse(root, root.val);return count;}private void traverse(TreeNode root, int pathMax) {if (root == null) {return;}// Find a "good node"if (pathMax <= root.val) {count++;// Update the maximum value on the pathpathMax = Math.max(root.val, pathMax);}traverse(root.left, pathMax);traverse(root.right, pathMax);}
}