题解 | #二叉树中和为某一值的路径(三)#

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
#include <cmath>
#include <cstddef>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param sum int整型 
     * @return int整型
     */
    int path_tr(TreeNode* tr, int sum){
        // 记录从tr节点开始，和为sum的路径的条数
        if(tr == NULL){
            return 0;
        }
        int res = 0;
        int leaveVal = sum - tr->val;
        if(leaveVal == 0){
            res += 1;
            res += 1* path_tr(tr->left, 0) + path_tr(tr->right, 0);
            return res;
        }
        res = path_tr(tr->left, leaveVal) + path_tr(tr->right, leaveVal);
        return res;
    }

    void inOrder(TreeNode* root, int& pathNum, int sum){
        //中序遍历以root为根节点的二叉树，并记录从每个节点开始的路径和为sum的路径条数添加到pathNum中。其中pathNum是全局变量
        if(root == NULL){
            pathNum += 0;
            return;
        }
        pathNum += path_tr(root, sum);
        inOrder(root->left, pathNum, sum);
        inOrder(root->right, pathNum, sum);

    }
    int FindPath(TreeNode* root, int sum) {
        int pathNum = 0;
        inOrder(root, pathNum,  sum);
        return pathNum;
        // write code here
    }
};

使用递归一遍过，还挺自豪的。