2023-08-25每日一题
一、题目编号
1448. 统计二叉树中好节点的数目
二、题目链接
点击跳转到题目位置
三、题目描述
给你一棵根为 root 的二叉树，请你返回二叉树中好节点的数目。
「好节点」X 定义为：从根到该节点 X 所经过的节点中，没有任何节点的值大于 X 的值。
示例 1：
示例 2：
示例 3：
提示：
- 二叉树中节点数目范围是 [1, 105] 。
- 每个节点权值的范围是 [-104,104] 。
四、解题代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
int dfs(TreeNode* &root, int &max_num){
if(root == nullptr){
return 0;
}
if(root->val < max_num){
return dfs(root->left, max_num)+dfs(root->right, max_num);
}
return 1 + dfs(root->left, root->val) + dfs(root->right, root->val);
}
public:
int goodNodes(TreeNode* root) {
return dfs(root, root->val);
}
};
五、解题思路
(1) 因为题目中是在树中进行问题解决的，所以需要使用树的遍历。
(2) 因为所以寻找的点是从根节点到当前节点没有比当前节点大的，最大节点一开始设置为根结点。如果遍历到的节点小于根结点，那么最大节点值不需要更新，并且剩余符合要求的需要从左子树和右子树中找。如果当前节点大于等于目前已经更新的最大节点，则最大节点的值更新，并且最终的结果是1（当前遍历到的节点满足要求）+ 左子树和右子树中所有满足要求的节点。文章来源：https://www.toymoban.com/news/detail-671516.html
(3) 返回结果即可。文章来源地址https://www.toymoban.com/news/detail-671516.html
到了这里，关于2023-08-25 LeetCode每日一题（统计二叉树中好节点的数目）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
