【JZ82 二叉树中和为某一值的路径

描述

给定一个二叉树 root 和一个值 sum ，判断是否有从根节点到叶子节点的节点值之和等于 sum 的路径。

1. 该题路径定义为从树的根结点开始往下一直到叶子结点所经过的结点
2. 叶子节点是指没有子节点的节点
3. 路径只能从父节点到子节点，不能从子节点到父节点
4. 总节点数目为n

例如：
给出如下的二叉树，sum=22，

返回true，因为存在一条路径 5→4→11→2 的节点值之和为 22

数据范围：
1.树上的节点数满足 0 ≤ n ≤ 10000
2.每 个节点的值都满足 ∣val∣ ≤ 1000
要求：空间复杂度 O(n)，时间复杂度 O(n)
进阶：空间复杂度 O(树的高度)，时间复杂度 O(n)

示例1

输入： {5,4,8,1,11,#,9,#,#,2,7},22

返回值：true

示例2

输入： {1,2},0

返回值：false

示例3

输入： {1,2},3

返回值：true

示例4

输入： {},0

返回值：false

算法思想：递归

解题思路：
采用递归遍历二叉树的路径节点，同时计算二叉树路径节点的数字之和，当到达叶子节点且路径的数字之和等于 sum 则说明二叉树中存在节点和为指定值的路径

算法步骤：

1. 特殊情况：当二叉树为空，则返回 false
2. 遍历根节点的左右子树，记录根节点的数字之和 res,当节点的左右子树均为空，且 res == sum，则返回 true
3. 递归 该节点的左右子树，做上述计算

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @param sum int整型 
     * @return bool布尔型
     */
    bool hasPathSum(TreeNode* root, int sum) {
         //空结点找不到路径 fast-template
        if(root == NULL)
            return false;
        //叶子结点，且路径和为sum
        if(root->left == NULL && root->right == NULL && sum - root->val == 0)
            return true;
        //递归进入子结点
        return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val);
    }
};

运行时间：6ms
超过33.26% 用C++提交的代码
占用内存：768KB
超过56.98%用C++提交的代码