Path Sum

Path Sum

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.

遞歸進行深度搜索

原題鏈接

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

 	}
 };