BM29. [二叉树中和为某一值的路径(一)]
https://www.nowcoder.com/exam/oj?tab=%E7%AE%97%E6%B3%95%E7%AF%87&topicId=295
BM29. 二叉树中和为某一值的路径(一)
题目的主要信息：
- 给定一个二叉树root和一个值 sum ，判断是否有从根节点到叶子节点的节点值之和等于 sum 的路径
- 路径定义为从树的根结点开始往下一直到叶子结点所经过的结点
- 路径只能从父节点到子节点，不能从子节点到父节点
- 要求：空间复杂度
，时间复杂度
递归
具体做法：
可以使用递归先序遍历，每次检查遍历到的结点是否为叶子结点，且当前sum值等于结点值，如果可以则返回true；如果不行，则检查左右子节点是否可以有完成路径的，如果任意一条路径可以都返回true，因此这里选用两个子节点递归的或。
if(root == null)
return false;
int result = sum - root.val;
if(result == 0 && root.left == null && root.right == null)
return true;
//遍历左子树
boolean left= hasPathSum(root.left, result);
//遍历右字树
boolean right = hasPathSum(root.right, result);
return left || right;
class Solution {
public:
bool hasPathSum(TreeNode* root, int sum) {
if(root == NULL) //空结点找不到路径
return false;
if(root->left == NULL && root->right == NULL && sum - root->val == 0) //叶子结点，且路径和为sum
return true;
return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val); //递归进入子结点
}
};
复杂度分析：
- 时间复杂度：
- 空间复杂度：
