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,

  1.               5
  2.              / \
  3.             4   8
  4.            /   / \
  5.           11  13  4
  6.          /  \      \
  7.         7    2      1

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

题目翻译:
给定一颗二叉树和一个特定值，写一个方法来判定这棵树是否存在这样一种条件，使得从root到其中一个叶子节点的路径的和等于给定的sum值.

解题思路:
这道题很常规，直接用DFS就可以求解.

时间复杂度:
O(n)

代码如下:

  1. /**
  2.  * Definition for binary tree
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  8.  * };
  9.  */
  10. class Solution {
  11. public:
  12.     bool hasPathSum(TreeNode *root, int sum) {
  13.         if(root == NULL)
  14.             return false;
  15.         return DFS(sum, 0, root);
  16.     }
  18.     bool DFS(int target, int sum, TreeNode* root)
  19.     {
  20.         if(root == NULL)
  21.             return false;
  22.         sum += root->val;
  23.         if(root->left == NULL && root->right == NULL)
  24.         {
  25.             if(sum == target)
  26.                 return true;
  27.             else
  28.                 return false;
  29.         }
  30.         bool leftPart = DFS(target, sum, root->left);
  31.         bool rightPart = DFS(target, sum, root->right);
  32.         return leftPart||rightPart;
  33.     }
  35. };