当前位置：首页 > backend >正文

Day94 | 灵神 | 二叉树统计二叉树中好点的数目

backend 2025/5/21 5:33:16

Day94 | 灵神 | 二叉树统计二叉树中好点的数目

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

1448. 统计二叉树中好节点的数目 - 力扣（LeetCode）

思路：

1.递归函数含义

含义就是以t为根结点的子树中有多少个好点

这个一般就和题目要求的东西是一样的

2.参数以及返回值

int tra(TreeNode* t,int max)

传入的是根节点以及已经走过的路径的最大值

返回值就是以t为根结点的子树中有多少个好点

3.终止条件

if(t==nullptr)return 0;

如果是空节点那肯定不可能有好点了

4.本层逻辑

显然，以t为根结点的好点数量就等于左子树好点数和右子树好点数之和，但是这里还要看当前结点t是否也是好点，是的话那就更新最大值，在左右子树之和基础上再+1，不是的话就不加

		if(t->val>=max){max=t->val;return tra(t->left,max)+tra(t->right,max)+1;}return tra(t->left,max)+tra(t->right,max);

完整代码：

浅浅记录笔者自己的代码

class Solution {
public:int tra(TreeNode* t,int max){if(t==nullptr)return 0;if(t->val>=max){max=t->val;return tra(t->left,max)+tra(t->right,max)+1;}return tra(t->left,max)+tra(t->right,max);}int goodNodes(TreeNode* root) {return tra(root,INT_MIN);}
};

灵神写的简洁版代码

class Solution {
public:int goodNodes(TreeNode *root, int mx = INT_MIN) {if (root == nullptr)return 0;int left = goodNodes(root->left, max(mx, root->val));int right = goodNodes(root->right, max(mx, root->val));return left + right + (mx <= root->val);}
};