拿不准的遍历顺序，搞不清的回溯过程，我太难了！ | LeetCode：112.

Leetcode 112.路径总和：递归函数没有返回值也是可以的（leetcode 8ms）

class Solution {

public:

    bool hasPath = false; // 定义一个全局结果变量

    void backtracking(TreeNode* root, int pathSum, int targetSum) {

        if (hasPath) return; // 如果已经找到 不在继续递归遍历

        if (!root->left && !root->right) {

            if (pathSum == targetSum) hasPath = true;

            return;

        }

        if (root->left) {

            pathSum += root->left->val;

            backtracking(root->left, pathSum, targetSum);

            pathSum -= root->left->val;

        }

        if (root->right) {

            pathSum += root->right->val;

            backtracking(root->right, pathSum, targetSum);

            pathSum -= root->right->val;

        }

    }

    bool hasPathSum(TreeNode* root, int targetSum) {

        if (!root) return false;

        backtracking(root, root->val, targetSum);

        return hasPath; // 返回结果

    }

};