题目描述
Given a binary tree root, a node X in the tree is named good if in the path from root to X there are no nodes with a value greater than X.
Return the number of good nodes in the binary tree.
Examplre1
Input: root = [3,1,4,3,null,1,5] Output: 4 Explanation: Nodes in blue are good. Root Node (3) is always a good node. Node 4 -> (3,4) is the maximum value in the path starting from the root. Node 5 -> (3,4,5) is the maximum value in the path Node 3 -> (3,1,3) is the maximum value in the path.
Examplre2
Input: root = [3,3,null,4,2] Output: 3 Explanation: Node 2 -> (3, 3, 2) is not good, because “3” is higher than it.
递归版本解题思路
- 递归思想，将当前路径的最大值往下传，然后进行判断即可
/**
* 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 {
public:
int goodNodes(TreeNode* root) {
if(root == nullptr){
return 0;
}
return funHelper(root, root -> val);
}
int funHelper(TreeNode* root, int maxVal){
int res = 0;
if(root -> val >= maxVal){
res = 1;
maxVal = root -> val;
}
if(root -> left){
res += funHelper(root -> left, maxVal);
}
if(root -> right){
res += funHelper(root -> right, maxVal);
}
return res;
}
};
