Path Sum(参考别人，二叉树DFS)

爱被打了一巴掌 2022-01-06 07:19 194阅读 0赞

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example:  
Given the below binary tree and `sum = 22`,

5
                 / \
                4   8
               /   / \
              11  13  4
             /  \      \
            7    2      1

return true, as there exist a root-to-leaf path `5->4->11->2` which sum is 22.

--------------------

1.刚开始的错误思路~ 每个人都有水比的过去，虽然现在仍然很水。题目要求必须是根到叶子，也就是说只要某个节点仍然有叶节点就要继续往下走。如下的代码错在res是个全局变量，它在递归下降过程和回溯过程的值一直在改变，具体这个代码就是其实res最后的值是所有节点值相加的总和，所以知道错在哪里，就好修改了。

class Solution {
    private:
        int res;
        int mysum;
    public:
        bool tra(TreeNode* root)
        {
            if(root==NULL)
                return false;
            res+=root->val;
            if(res==mysum)
                return true;
            return tra(root->left)||tra(root->right);
        }
        bool hasPathSum(TreeNode *root, int sum) {
            res=0;
            mysum=sum;
            return tra(root);
            
        }
    };

2.改过后的AC代码，在递归过程需要变动的值，是应该当做参数来传递。由于sum是局部变量，所以在回溯的时候，该值不会像全局变量和静态变量那样，而它会回溯成该节点处本来的值，画个小图来说明一下：

![282134480035476.png][]

class Solution {
    private:
        int mysum;
    public:
        bool tra(TreeNode* root,int sum)
        {
            if(root==NULL){
                return false;
            }
            sum+=root->val;
            if(sum==mysum&&root->left==NULL&&root->right==NULL){
                return true;
            }
            return tra(root->left,sum)||tra(root->right,sum);
        }
    
        bool hasPathSum(TreeNode *root, int sum) 
        { 
            mysum=sum;
            return tra(root,0);
        }
    };

3.递归详解和静态变量的描述

静态变量：static int a=3;加上static之后，该变量的生命周期发生了改变，不再是局部变量，而是整个文件执行完毕，该变量才释放。

递归详解（转）：

一、栈  
在说函数递归的时候，顺便说一下栈的概念。  
栈是一个后进先出的压入(push)和弹出(pop)式数据结构。在程序运行时，系统每次向栈中压入一个对象，然后栈指针向下移动一个位置。当系统从栈中弹出一个对象时，最近进栈的对象将被弹出。然后栈指针向上移动一个位置。程序员经常利用栈这种数据结构来处理那些最适合用后进先出逻辑来描述的编程问题。这里讨论的程序中的栈在每个程序中都是存在的，它不需要程序员编写代码去维护，而是由运行是系统自动处理。所谓的系统自动维护，实际上就是编译器所产生的程序代码。尽管在源代码中看不到它们，但程序员应该对此有所了解。  
再来看看程序中的栈是如何工作的。当一个函数(调用者)调用另一个函数(被调用者)时，运行时系统将把调用者的所有实参和返回地址压入到栈中，栈指针将移到合适的位置来容纳这些数据。最后进栈的是调用者的返回地址。当被调用者开始执行时，系统把被调用者的自变量压入到栈中，并把栈指针再向下移，以保证有足够的空间存储被调用者声明的所有自变量。当调用者把实参压入栈后，被调用者就在栈中以自变量的形式建立了形参。被调用者内部的其他自变量也是存放在栈中的。由于这些进栈操作，栈指针已经移动所有这些局部变量之下。但是被调用者记录了它刚开始执行时的初始栈指针，以他为参考，用正或负的偏移值来访问栈中的变量。当被调用者准备返回时，系统弹出栈中所有的自变量，这时栈指针移动了被调用者刚开始执行时的位置。接着被调用者返回，系统从栈中弹出返回地址，调用者就可以继续执行了。当调用者继续执行时，系统还将从栈中弹出调用者的实参，于是栈指针回到了调用发生前的位置。  
可能刚开始学的人看不太懂上面的讲解，栈涉及到指针问题，具体可以看看一些数据结构的书。要想学好编程语言，数据结构是一定要学的。  
  
二、递归  
递归，是函数实现的一个很重要的环节，很多程序中都或多或少的使用了递归函数。递归的意思就是函数自己调用自己本身，或者在自己函数调用的下级函数中调用自己。  
递归之所以能实现，是因为函数的每个执行过程都在栈中有自己的形参和局部变量的拷贝，这些拷贝和函数的其他执行过程毫不相干。这种机制是当代大多数程序设计语言实现子程序结构的基础，是使得递归成为可能。假定某个调用函数调用了一个被调用函数，再假定被调用函数又反过来调用了调用函数。这第二个调用就被称为调用函数的递归，因为它发生在调用函数的当前执行过程运行完毕之前。而且，因为这个原先的调用函数、现在的被调用函数在栈中较低的位置有它独立的一组参数和自变量，原先的参数和变量将不受影响，所以递归能正常工作。程序遍历执行这些函数的过程就被称为递归下降。  
程序员需保证递归函数不会随意改变静态变量和全局变量的值，以避免在递归下降过程中的上层函数出错。程序员还必须确保有一个终止条件来结束递归下降过程，并且返回到顶层。  
例如这样的程序就是递归：

void a(int);
    
             main()
             {
                 int num=5;
                 a(num);
             }
    
             void a(int num)
             {
                 if(num==0) return;
                 printf("%d",num);
                 a(--num);
             }

在函数a()里面又调用了自己，也就是自己调用本身，这样就是递归。那么有些人可能要想，这不是死循环吗？所以在递归函数中，一定要有return语句，没有return语句的递归函数是死循环。  
我们分析上面的例子，先调用a(5)，然后输出5，再在函数中调用本身a(4)，接着回到函数起点，输出4，……，一直到调用a(0)，这时发现已经满足if条件，不在调用而是返回了，所以这个递归一共进行了5次。如果没有这个return，肯定是死循环的。  
虽然递归不难理解，但是很多在在使用递归函数的时候，问题多多。这里面一般有两个原因：一是如何往下递归，也就是不知道怎么取一个变量递归下去；二是不知道怎么终止递归，经常弄个死循环出来。  
下面看几个例子：  
1.求1+2+……+100的和  
先分析一下。第一递归变量的问题，从题目上看应该取1,2,……,100这些变量的值作为递归的条件；第二就是如何终止的问题，从题目上看应该是当数为100的时候就不能往下加了。那么我们试着写一下程序。

int add(int);
    
             main()
             {
                 int num=1,sn;
                 sn=add(num);
                 printf("%d/n",sn);
                 getch();
             }
    
             int add(int num)
             {
                 static int sn;
                 sn+=num;
                 if(num==100) return sn;
                 add(++num);
             }

分析一下程序：前调用add(1)，然后在子函数中把这个1加到sn上面。接着调用add(2)，再把sn加2上来。这样一直到100，到了100的时候，先加上来，然后发现满足了if条件，这时返回sn的值，也就是1+2+……+100的值了。  
这里有一个问题一定要注意，就是static int sn;  
有些人就不明白，为什么要使用static类型修饰符，为什么不使用int sn=0;？如果使用int sn=0;这样的语句，在每次调用函数add()的时候，sn的值都是赋值为0,也就是第一步虽然加了1上来，可是第二次调用的时候，sn又回到了0。我们前面说了，static能保证本次初始化的值是上次执行后的值，这样也就保证了前面想加的结果不会丢失。如果你修改为int sn=0，最后结果一定是最后的100这个值而不是5050。  
  
2.求数列s(n)=s(n-1)+s(n-2)的第n项。其中s(1)=s(2)=1。  
可以看出，终止条件一定是s(1)=s(2)=1。递归下降的参数一定是n。  
  
int a(int);  
  
main()  
\{  
int n,s;  
scanf("%d",&n);  
s=a(n);  
printf("%d/n",s);  
getch();  
\}  
  
int a(int n)  
\{  
if(n<3) return 1;  
return a(n-1)+a(n-2);  
\}  
  
这个题目主要说明的是，在函数中，不一定只有一个return语句，可以有很多，但是每次对归的时候只有一个起作用。题目不难理解，这儿不分析了。  
说了这些递归，其实它和函数的调用没有大的区别，主要就是一个终止条件要选好。递归函数很多时候都能用循环来处理。  
  
main()  
\{  
int n=20,array\[20\];  
int i;  
for(i=0;i<n;i++)  
\{  
if(i<2) array=1;  
else array=array+array;  
\}  
printf("%d/n",array\[19\]);  
getch();  
\}  
  
上面的程序就是实现一模一样的功能的。但是它有一个缺陷，就是n的值不是通过键盘输入来得到。如果想通过键盘来得到n，可以这样：  
  
main()  
\{  
int n,i;  
int s1=1,s2=1,temp  
scanf("%d",&n);  
for(i=3;i<=n;i++)  
\{  
temp=s2;  
s2+=s1;  
s1=temp;  
\}  
printf("%d/n",s2);  
getch();  
\}  
  
但是在某些场合，使用递归比使用循环要简单的多。而且有些题目，一看就知道应该使用递归而不是循环来处理。

转载于:https://www.cnblogs.com/fightformylife/p/4058000.html

[282134480035476.png]: /images/20211227/649bbc4b881b4f529ac49a2cd9c37d96.png