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(当前遍历到的节点满足要求)+ 左子树和右子树中所有满足要求的节点。
(3) 返回结果即可。