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

由于要找到路径中的最大值，因此我们可以用深度优先搜索。在每一条路径的探索过程中，维护路径中的最大值path_max，并将其与当前节点的值val作比较。如果val大于path_max，那么这个节点就是好节点。

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

写dfs是绕不开递归的。写二叉树中的递归，要对计算方式有一个大概的感知。将传入的节点视为叶子节点（或叶子节点的子节点），确定递归终止条件；再将传入的节点视为一个处在中间位置的节点，搞清楚递归的意思。

以此题为例。我们可以看到，每一棵（子）树的根节点都对应的一个值，我们称之为value，这个value代表的是以该节点为根节点的树中“好节点”的个数。那么，对于一个非叶子节点root来说，它的value正是其左孩子的value加上右孩子的value，如果这个叶子节点本身也是”好节点“，那么还要再+1。走到这里，我们对整道题的计算方式已经有了一个整体的感知。

接下来就好说了。由于对于传入的节点root，我们需要计算其左孩子的value和右孩子的value，那么必然要传入root->left和root->right。如果root是叶子节点，那么root->left和root->right都为nullptr.这时候，root的value就很显然了，如果它是好节点，那么就为1，否则为0.这是可以直接return的。所以递归终止条件就是root==nullptr

那么，对于一个普通的处于中间层的节点，当它的value被计算出来后，就会return，给它的父亲节点去计算，它的使命也就完成了，逻辑合理，没有问题。

所以递归的写法是：res+=dfs(root->left,path_max)+dfs(root->right,path_max);

1457. 二叉树中的伪回文路径 - 力扣（LeetCode）

首先，我们肯定需要判断一个序列是不是伪回文列。我们定义一个bool类型的函数check去判断。先想逻辑。伪回文列什么意思？如果一个序列中的数可以在经历排列后成为回文列，那么这个序列就称为伪回文列。而我们知道，回文列是中心对称的。如果对称中心只有一个数，那么只有这一个数出现了奇数次，其它都为偶数次。如果对称中心是两个数，那么没有数出现了奇数次。所以说，我们需要建立一个数组，统计一个序列中每个数出现的频率。

    bool check(vector<int>&fre)
    {
        int odd=0;
        for(int x:fre)
        {
            if(x%2==1)
            {
                odd++;
            }
        }
        return odd<=1;//伪回文串中至多只能有一个元素出现次数为奇数
    }

这里我们直接传入了这个记录各个数出现次数的数组fre.

接下来，我们要找到fre要统计的数组。根据题意，这个数组就是每一条路径中的元素。所以，在深度优先搜索的过程中，当我们发现我们传入的是叶子节点，就可以对这个数组进行check了。如果check返回true，那么答案自增1.如果传入的不是叶子节点，就递归调用其左孩子与右孩子。

class Solution 
{
public:
    bool check(vector<int>&fre)
    {
        int odd=0;
        for(int x:fre)
        {
            if(x%2==1)
            {
                odd++;
            }
        }
        return odd<=1;//伪回文串中至多只能有一个元素出现次数为奇数
    }
    int dfs(TreeNode*root,vector<int>&cnt)
    {
        if(root==nullptr)
        {
            return 0;
        }
        cnt[root->val]++;
        int res=0;
        if(root->left==nullptr&&root->right==nullptr)
        {
            if(check(cnt))
            {
                res++;
            }
        }
        else
        {
            res+=dfs(root->left,cnt)+dfs(root->right,cnt);
        }
        cnt[root->val]--;
        return res;
    }
    int pseudoPalindromicPaths (TreeNode* root) 
    {
        vector<int>cnt(10);
        return dfs(root,cnt);
    }
};

这里需要注意的是cnt[root->val]--.为什么要有这一步操作？这是因为，对于每一个节点来说都有一个属于自己的cnt数组（值意义上的，不是空间意义上的）。我们用题目的例子说明一下。当cnt数组为{2,3,3}时，我们已经处理完了，接下来应该处理{2,3,1}了，因此要把最后的3删除掉。实际上就是一个回溯的过程。