路径总和

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

经验1：

如果一段程序写在递归的上方，代表这一层函数压栈时(也就是这层递归开始运行时)运行这段程序

int fun(int n) {
    static int i = 0;
    if (n == 1) return 1;
    if (n == 4) return i;
    i++;
    fun(n - 1);
    return i;
}
int main() {
    cout << fun(5) << endl;
}

运行结果为1

如果一段程序写在递归的下方，代表上一层函数函数弹栈时(也就是上一层递归运行结束后)运行这段程序

int fun(int n) {
    static int i = 0;
    if (n == 1) return 1;
    i++;
    fun(n - 1);
    if (n == 4) return i;
    return i;
}
int main() {
    cout << fun(5) << endl;
}

运行结果为4

经验2：什么叫回溯，以及回溯的作用

• 回溯就是左子树运行的时候会改变某个变量的值，比如此题的targetSum(一定注意传递targetSum要用引用传递，保证传到递归函数中的还是函数最开始传进来的那个targetSum)，左子树运行完之后要加一行代码(这行代码就是回溯)，将该变量的值改为左子树运行之前的值。回溯的作用就是让左右子树操作同一个变量是互相不影响。

 1 bool hasPathSum(TreeNode* root, int& targetSum) {
 2     if (root == nullptr) return false;
 3     targetSum -= root->val;
 4     if (root->left == nullptr && root->right == nullptr && targetSum == 0) return true;
 5     if (root->left == nullptr && root->right == nullptr && targetSum != 0) return false;
 6     if (root->left) {
 7         bool leftresult = hasPathSum(root->left, targetSum);
 8         targetSum+=root->left->val;
 9         if (leftresult) return true;
10     }
11     if (root->right) {
12         bool rightresult = hasPathSum(root->right, targetSum);
13         targetSum+=root->right->val;
14         if (rightresult) return true;
15     }
16     return false;
17 }

• 可以不用回溯吗，可以！我们可以将递归函数进行值传递，这样运行到左子树的递归时实参经过左子树的这一层函数不会发生改变，等传给右子树的递归还会保持左子树的递归之前的那个值。

 1 bool hasPathSum(TreeNode* root, int targetSum) {
 2     if (root == nullptr) return false;
 3     targetSum -= root->val;
 4     if (root->left == nullptr && root->right == nullptr && targetSum == 0) return true;
 5     if (root->left == nullptr && root->right == nullptr && targetSum != 0) return false;
 6 
 7     if (root->left) {
 8         bool leftresult = hasPathSum(root->left, targetSum);
 9 
10         if (leftresult) return true;
11     }
12     if (root->right) {
13         bool rightresult = hasPathSum(root->right, targetSum);
14 
15         if (rightresult) return true;
16     }
17     return false;
18 }

也就是说值传递=引用传递+回溯，但是引用传递+回溯是更好的选择，因为我每递归一次就得开辟一个新的targetSum，随着递归层数的增加，我们就会出现栈溢出