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

C语言， 递归

bool recursion(struct TreeNode* node, int target){

    static int sum = 0;

    int lastNode;

    if(!node)return false;  //根节点为空

    sum += node->val;       //将当前节点的值加入sum

    // if(sum > target)return false;        //bug：节点有负数，因此不能判断当前值大于目标值就退出

    if(sum == target && !node->left && !node->right)return true;    //到达叶子节点并且当前值与目标值相等，返回true

    if(node->left){     //如果左子节点存在，进行递归

        if(true == recursion(node->left, target)) return true;  //如果递归返回true，则继续返回true，直到最上层跳出函数

        sum -= node->left->val; //运行到这里表示上一次递归返回了，需要减去上一次递归的node节点的值

    }

    if(node->right){

        if(true == recursion(node->right, target)) return true;

        sum -= node->right->val;

    }

    return false;   //运行到这里，说明当前node左右子节点的路径都不满足返回false,跳回当前节点的父节点。(如果到根节点则退出函数返回false)

}

bool hasPathSum(struct TreeNode* root, int sum ) {

    // write code here

    return recursion(root, sum);    //输入根节点与目标值进行递归

}