2023-08-25每日一题

一、题目编号

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

二、题目链接

点击跳转到题目位置

三、题目描述

给你一棵根为 root 的二叉树，请你返回二叉树中好节点的数目。

「好节点」X 定义为：从根到该节点 X 所经过的节点中，没有任何节点的值大于 X 的值。

示例 1：

示例 2：

示例 3：

提示：

• 二叉树中节点数目范围是 [1, 10⁵] 。
• 每个节点权值的范围是 [-10⁴,10⁴] 。

四、解题代码

/*** 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) 返回结果即可。