1.题目描述
描述
给定一个二叉树root和一个值 sum ，判断是否有从根节点到叶子节点的节点值之和等于 sum 的路径。
该题路径定义为从树的根结点开始往下一直到叶子结点所经过的结点
叶子节点是指没有子节点的节点
路径只能从父节点到子节点，不能从子节点到父节点
总节点数目为n
例如：
给出如下的二叉树，s u m = 22 sum=22sum=22，
返回true，因为存在一条路径 5 → 4 → 11 → 2 5\to 4\to 11\to 25→4→11→2的节点值之和为 22。
数据范围：
1.树上的节点数满足 0 ≤ n ≤ 10000 0 \le n \le 100000≤n≤10000
2.每个节点的值都满足∣ v a l ∣ ≤ 1000 |val| \le 1000∣val∣≤1000
要求：空间复杂度 O ( n ) O ( n ) O(n)O(n)O(n)O(n)，时间复杂度O ( n ) O ( n ) O(n)O(n)O(n)O(n)
进阶：空间复杂度 O ( 树的高度 ) O ( 树的高度 ) O(树的高度)O(树的高度)O(树的高度)O(树的高度)，时间复杂度 O ( n ) O ( n ) O(n)O(n)O(n)O(n)
2.算法设计思路
核心其实就是一个二叉树的遍历。可以采用回溯法，在遍历树的过程中，利用一个全局变量num记录遍历到当前节点时路径上所有值的和。
当以当前结点为根的子二叉树中没有符合要求的叶子结点时，就向上回溯（从父结点到子结点时，num的值增加了；因此返回时就减去相应的值。）
3.代码实现
注：这里并不是完整代码，而只是核心代码的模式
/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param root TreeNode类 * @param sum int整型 * @return bool布尔型 */ int num = 0; bool hasPathSum(struct TreeNode* root, int sum ) { // write code here bool flag = false; if(root == NULL){return false;} num += root->val; //printf("num:%d\n", num); if(num == sum && root->left == NULL && root->right == NULL){return true;} //查找左右子树 if(hasPathSum(root->left, sum) == true){return true;} else {flag = true;} if(hasPathSum(root->right, sum) == true){return true;} else {flag = true;} //回溯 if(flag == true){ num -= root->val; return false; } //最后不加个返回，就会显示编译错误。其实前面逻辑上是一定会有返回值的 printf("error\n"); return false; }
当没有最后一行代码return false;时，就会显示如下的编译错误，避坑（代码其实应该是没有问题的）。
4.运行结果
成功通过！
