合肥公司制作网站的,无锡全网营销方案,网站开发系统的可行性研究报告,个人简介代码网页制作模板题目
给你一棵根为 root 的二叉树#xff0c;请你返回二叉树中好节点的数目。
「好节点」X 定义为#xff1a;从根到该节点 X 所经过的节点中#xff0c;没有任何节点的值大于 X 的值。
示例 1#xff1a; 输入#xff1a;root [3,1,4,3,null,1,5]
输出#xff1a;4
…题目
给你一棵根为 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) {return dfs(root, Integer.MIN_VALUE);}public int dfs(TreeNode root, int max) {if (root null) {return 0;}if (max root.val) {return dfs(root.left, max) dfs(root.right, max);}return dfs(root.left, root.val) dfs(root.right, root.val) 1;}
}
总结
深度遍历的时候记录前面最大的节点值和当前节点进行比较。我蠢的……一开始把前面所有节点值全给记录下来了然后一个个对比。
