C++刷LeetCode（1448. 统计二叉树中好节点的数目）【树】【递归】

糖逗

题目描述：

1. 给你一棵根为 root 的二叉树，请你返回二叉树中好节点的数目。
   
2. 
   
3. 「好节点」X 定义为：从根到该节点 X 所经过的节点中，没有任何节点的值大于 X 的值。
   
4. 
   
5.  
   
6. 
   
7. 示例 1：
   
8. 
   
9. 
   
10. 
    
11. 输入：root = [3,1,4,3,null,1,5]
    
12. 输出：4
    
13. 解释：图中蓝色节点为好节点。
    
14. 根节点 (3) 永远是个好节点。
    
15. 节点 4 -> (3,4) 是路径中的最大值。
    
16. 节点 5 -> (3,4,5) 是路径中的最大值。
    
17. 节点 3 -> (3,1,3) 是路径中的最大值。
    
18. 示例 2：
    
19. 
    
20. 
    
21. 
    
22. 输入：root = [3,3,null,4,2]
    
23. 输出：3
    
24. 解释：节点 2 -> (3, 3, 2) 不是好节点，因为 "3" 比它大。
    
25. 示例 3：
    
26. 
    
27. 输入：root = [1]
    
28. 输出：1
    
29. 解释：根节点是好节点。
    
30.  
    
31. 
    
32. 提示：
    
33. 
    
34. 二叉树中节点数目范围是 [1, 10^5] 。
    
35. 每个节点权值的范围是 [-10^4, 10^4] 。
    
36. 
    
37. 来源：力扣（LeetCode）
    
38. 链接：https://leetcode-cn.com/problems/count-good-nodes-in-binary-tree
    
39. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. /**
   
2. * Definition for a binary tree node.
   
3. * struct TreeNode {
   
4. *     int val;
   
5. *     TreeNode *left;
   
6. *     TreeNode *right;
   
7. *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
   
8. *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
   
9. *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
   
10. * };
    
11. */
    
12. class Solution {
    
13. public:
    
14.     void dfs(TreeNode* root, int max_val, int& res){
    
15.         if(root == NULL)return;
    
16.         if(root -> val >= max_val)res++;
    
17.         max_val = max(max_val, root -> val);
    
18.         dfs(root -> left, max_val, res);
    
19.         dfs(root -> right, max_val, res);
    
20.     }
    
21.     int goodNodes(TreeNode* root) {
    
22.         //树的递归
    
23.         int res = 0;
    
24.         dfs(root, root -> val, res);
    
25.         return res;
    
26.     }
    
27. };

复制代码