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

思路：递归调用+深搜

先是判断顶端是否为空，接着判断两个孩子是否为空，为空，加之前的数字，返回true或者false。

如果不为空，说明有左边和右边，先是判断左边，再是判断右边，不管顺序，总之是会返回的。

以其中一个为例，继续递归调用，看是否为真，为真，返回真，绝对不能直接返回 （用相等的判断语句）。因为不知道另外一半的情况，不能轻易下结论。

代码：

/**
 * 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:
//https://leetcode.com/problems/path-sum/
    bool hasPathSum(TreeNode* root, int sum) {
        if(root==NULL){//主要是为了判断顶点
            return false;
        }
        
        if(root->left==NULL&&root->right==NULL){
            return root->val==sum;
        }
        
        //这边相当于经历了第一层
        //开始经历第二层
        
        if(root->left){
            root->left->val+=root->val;
            //这个时候递归调用这个函数
            if(hasPathSum(root->left,sum)){
                return true;
            }//不能写 return hasPathSum(root->left, sum) 的原因是，我左边不能通过，右边可能存在呢。
             //有更好，没有算了
        }
        
        if(root->right){
            root->right->val+=root->val;
            if(hasPathSum(root->right,sum)){
                return true;
            }
        }
        
        return false;//无论上面怎么调用，都没用，返回false
    }
};