BM29. [二叉树中和为某一值的路径(一)]

https://www.nowcoder.com/exam/oj?tab=%E7%AE%97%E6%B3%95%E7%AF%87&topicId=295

BM29. 二叉树中和为某一值的路径(一)

https://www.nowcoder.com/practice/508378c0823c423baa723ce448cbfd0c?tpId=295&sfm=github&channel=nowcoder

题目的主要信息：

• 给定一个二叉树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); //递归进入子结点
    }
};

复杂度分析：

• 时间复杂度：，先序遍历二叉树所有结点
• 空间复杂度：，最坏情况二叉树化为链表，递归栈空间最大为