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

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

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

思路：

1.递归函数含义

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

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

2.参数以及返回值

1
int tra(TreeNode* t,int max)

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

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

3.终止条件

1
2
if(t==nullptr)
	return 0;

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

4.本层逻辑

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

1
2
3
4
5
6
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);

完整代码：

浅浅记录笔者自己的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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);
    }
};

灵神写的简洁版代码

1
2
3
4
5
6
7
8
9
10
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);
    }
};