437. Path Sum III**【力扣】

题意理解

计算二叉树中等于固定数的路径个数。

问题分析

用递归

左中右三个部分考虑。

难点1：从任一个结点开始计算路径，怎么做？

难点2：必须从上往下，终点不一定是叶子，怎么破?

解法：还原到树的基本形态，根 + 左子树 + 右子树。从任一结点开始计算，看成是从根、左子树和右子树三者出发；从上往下，遍历的顺序就是先根再左右子树，终点不一定是叶子就是说增加参数保存当前的路径和，满足和的要求就可以认为找到一条路径。

其他

https://leetcode.com/problems/path-sum-iii/discuss/91877/C%2B%2B-5-Line-Body-Code-DFS-Solution

链接

int pathSum(TreeNode* root, int sum) {
        if (root == NULL)    //空树，返回0
        {
            return false;
        }
        return SumUp(root, 0, sum) + pathSum(root -> left, sum) + pathSum(root -> right, sum);    //计算任何根，左子树，右子树的路径和等于sum的个数，然后相加
    }
    int SumUp(TreeNode* root, int pre, int& sum)    //参数2等于已经累计的值
    {
        if (!root)    //空，说明没有满足条件的和
            return 0;
        pre = pre + root -> val;    //累计当前的和
        return (pre == sum) + SumUp(root -> left, pre, sum) + SumUp(root -> right, pre, sum);    //如果根等于和，路径+1,然后分别递归计算左右子树的累计和的路径总数
    }