112_路径总和

风扫地

1. /*
   
2. 给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
   
3. 
   
4. 说明: 叶子节点是指没有子节点的节点。
   
5. 
   
6. 示例:
   
7. 给定如下二叉树，以及目标和 sum = 22，
   
8. 
   
9.               5
   
10.              / \
    
11.             4   8
    
12.            /   / \
    
13.           11  13  4
    
14.          /  \      \
    
15.         7    2      1
    
16. 返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。
    
17. 
    
18. */

复制代码

风扫地

常规的递归算法进行路径搜索。

1. bool g_ret_val = false;
   
2. int  g_sum     = 0;
   
3. 
   
4. void __path_sum(struct TreeNode* p , int cur_sum)
   
5. {
   
6.    
   
7.     if(p==NULL)
   
8.     {
   
9.         return ;
   
10.     }
    
11.    
    
12.     cur_sum += p->val;
    
13.     if(  (p->left==NULL)
    
14.        &&(p->right==NULL)   /*必须是叶子节点才进行判断*/
    
15.     )
    
16.     {
    
17.         if(cur_sum == g_sum)
    
18.         {
    
19.             g_ret_val = true;
    
20.         }
    
21.     }
    
22.     if(!g_ret_val)
    
23.     {
    
24.         __path_sum(p->left,cur_sum);
    
25.     }
    
26.    
    
27.     if(!g_ret_val)
    
28.     {
    
29.         __path_sum(p->right,cur_sum);
    
30.     }   
    
31.     return ;   
    
32. }
    
33. 
    
34. bool hasPathSum(struct TreeNode* root, int sum)
    
35. {
    
36.     g_ret_val = false;
    
37.     g_sum     = sum;
    
38.    
    
39.     if(root!=NULL)
    
40.     {
    
41.         __path_sum(root,0);
    
42.     }
    
43.     return g_ret_val;
    
44. }
    

复制代码