【递归】12. leetcode 1448 统计二叉树中好节点的数目

1 题目描述

题目链接：统计二叉树中好节点的数目

2 解答思路

第一步：挖掘出相同的子问题  （关系到具体函数头的设计）
第二步：只关心具体子问题做了什么  （关系到具体函数体怎么写，是一个宏观的过程）
第三步：找到递归的出口，防止死递归  （关系到如何跳出递归）

2.1 相同的子问题（函数头设计）

相同的子问题：统计二叉树中好节点的数目，就是统计左子树中好节点的数目 加上 右子树中好节点的数目

整体设计：
每次递归的时候需要传递二叉树和走到当前位置过程中遇到的最大的值

因此，函数头的设计如下：

int dfs(TreeNode* root, int mx)
    {
    }

传入二叉树，和遇到的最大值，返回以当前节点为根节点的二叉树的好节点数目。

2.2 具体的子问题做了什么（函数体的实现）

根据之前的分析，具体的子问题做的事情：
1.统计左子树中好节点的数目
2.统计右子树中好节点的数目
3.返回以该节点为二叉树的好节点的数目（这里需要判断当前节点是不是好节点，同时这里也是递归的一个出口）

//返回二叉树中好节点的数目 = 左子树中好节点的数目 + 右子树中好节点的数目
    //1.如何判断是不是好节点
    //2.递归左右子树
    int dfs(TreeNode* root, int mx)
    {
        if (root == nullptr)
            return 0;
        
        //判断是不是好节点  --> mx表示这一路下来，所经过节点的最大值
        int left = dfs(root->left, max(mx, root->val));
        int right = dfs(root->right, max(mx, root->val));

        //返回当前节点的好节点的个数
        return left + right + (mx <= root->val);
    }

3 总结

class Solution {
public:
    int goodNodes(TreeNode* root) {
        return dfs(root, INT_MIN);
    }

    //返回二叉树中好节点的数目 = 左子树中好节点的数目 + 右子树中好节点的数目
    //1.如何判断是不是好节点
    //2.递归左右子树
    int dfs(TreeNode* root, int mx)
    {
        if (root == nullptr)
            return 0;
        
        //判断是不是好节点  --> mx表示这一路下来，所经过节点的最大值
        int left = dfs(root->left, max(mx, root->val));
        int right = dfs(root->right, max(mx, root->val));

        //返回当前节点的好节点的个数
        return left + right + (mx <= root->val);
    }
};