Path Sum--LeetCode

浅浅的花香味﹌ 2022-08-07 11:58 87阅读 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.

思路：利用递归的思路。

bool helper(BinTree* root,int key,int cur)
    {
    	if(root == NULL)
    		return 0;
    	cur+=root->value;
    	if(root->left == NULL && root->right == NULL)
    	{
    		if(cur==key)
    			return 1;
    		else
    			return 0;
    			
    	}	
    	if(root->left !=NULL && root->right ==NULL)
    		return helper(root->left,key,cur);
    	if(root->right !=NULL && root->left ==NULL)
    		return helper(root->right,key,cur);
    	if(root->right !=NULL && root->left!=NULL)
    		return helper(root->right,key,cur) || helper(root->left,key,cur);
    	
    }
    
    bool PathSum(BinTree* root,int key)
    {
    	int cur=0;
    	if(root== NULL)
    		return 0;
    	return helper(root,key,cur);
    	
    }

bool hasPathSum(BinTree*root, int sum) {  
            // Start typing your C/C++ solution below  
            // DO NOT write int main() function  
            if(root == NULL)  
            {  
                return false;  
            }  
            return pathSum(root, 0, sum);  
        }  
          
        bool pathSum(TreeNode * p, int total, int sum)  
        {  
            if((p->left == NULL) && (p->right == NULL))  
            {  
                if(total + p->val  == sum)  
                {  
                    return true;  
                }  
                else  
                {  
                    return false;  
                }  
            }  
            else if(p->left == NULL)  
            {  
                return pathSum(p->right, p->val + total, sum);  
            }  
            else if(p->right == NULL)  
            {  
                return pathSum(p->left, p->val + total, sum);  
            }  
            else  
            {  
                return pathSum(p->left, p->val + total, sum) || pathSum(p->right, p->val + total, sum);  
            }  
        }

bool PathSum_second(BinTree* root,int value)
    {
    	if(root==NULL)
    		return 0;
    	if(root->left ==NULL && root->right == NULL && root->value == value)
    		return 1;
    	else
    		return PathSum_second(root->left,value-root->value)||PathSum_second(root->right,value-root->value);
    }

ps; [ Sum Root to Leaf Numbers][Sum Root to Leaf Numbers]这个文章介绍了从根到节点的路径，那么我们也可以这么考虑，就是从根到叶子节点的路径的所有和是否等于给定的值来判断是否符合条件。

[Sum Root to Leaf Numbers]: http://blog.csdn.net/yusiguyuan/article/details/44957589