[leetcode]112. 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.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool hasPathSum(TreeNode* root, int sum) {
      }
};

题目翻译：

输入为一个二叉树及一个数值sum，你需要判断是否存在一条二叉树的路径满足从根节点开始一直到叶子节点结束，数值相加等于所给定的sum值。
例如：
给出如下二叉树，并且sum值为22，

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

结果应该返回true，因为存在 5->4->11->2 路径满足相加等于22.

问题解决：

这道题目的整体思路还算简单，因为直接需要判断的就是根节点到叶子结点的一条完整路径，而不需要考虑其中的某条子路径，那么，首先想到的就是DFS，先对左节点步步深入，如果不存在，再对右节点做相同的操作，因此就是一个不断地递归的过程,完整代码如下：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool hasPathSum(TreeNode* root, int sum) {
        if(!root && sum == 0) return false;
        else if(!root) return false;
        else if(root && !(root -> left) && !(root -> right) && sum == root->val) return true;
        else if(root)
        {
            if(hasPathSum(root -> left, sum - root->val))
            {
                return true;
            }
            if(hasPathSum(root -> right, sum - root->val))
            {
                return true;
            }
        }
        return false;
    }
};