X

LEETCODE 1448. Count Good Nodes in Binary Tree 解题思路分析

题目大意:

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

给你一棵根为 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]

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1448

解题思路分析:

这是一道典型使用dfs解决二叉树问题的题目。利用dfs深度优先搜索来递归遍历二叉树的每一个节点,并且在递归函数的参数中传入当前路径中的最大值max。如果当前节点大于等于max,说明当前节点属于一个好节点,当前递归的返回结果为1,同时更新max为当前节点。然后dfs递归至其左右两个子节点,并将递归结果累加至当前递归的返回结果。

实现代码:

public int goodNodes(TreeNode root) {
    return dfs(root,root.val); // dfs求解
}
// root:当前节点
// max:当前路径中最大值
int dfs(TreeNode root, int max){
    int res=0; // 返回结果
    if(root.val>=max){ // 如果当前节点大于等于max
        res=1; // 当前节点是一个好节点
        max=root.val; // 更新max值
    }
    if(root.left!=null){ // dfs递归至左子节点
        res+=dfs(root.left,max);
    }
    if(root.right!=null){ // dfs递归至右子节点
        res+=dfs(root.right,max);
    }
    return res;
}

本题解法执行时间为3ms。

Runtime: 3 ms, faster than 69.99% of Java online submissions for Count Good Nodes in Binary Tree.

Memory Usage: 55 MB, less than 100.00% of Java online submissions for Count Good Nodes in Binary Tree.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: https://leetcode.jp/leetcode-1448-count-good-nodes-in-binary-tree-解题思路分析/
Categories: leetcode
kwantong: