思路

本题实质上是一道二叉树搜索的问题，通过遍历搜索二叉树，从而判断二叉树节点中是否存在节点和为指定值的路径。

方法一：前序遍历

  • 这里采用的是前序遍历的递归实现方法，即：根节点-左儿子-右儿子。

  • 具体思路如下图所示：
Pythton 代码： 
class Solution:
    def hasPathSum(self , root: TreeNode, sum: int) -> bool:
        # write code here
        if root == None:
            return False
        if root.left == None and root.right == None and root.val == sum:
            return True
        return self.hasPathSum(root.left, sum-root.val)&nbs***bsp;self.hasPathSum(root.right, sum-root.val)

  • 时间复杂度为O(n)，n为二叉树节点数，即最坏的情况需要遍历二叉树的所有节点。

  • 空间复杂度为O(n)，最坏情况递归遍历所有节点N。
方法二：层次遍历

  • 同样我们也可以通过层次遍历，同步推进每一条路径在每一层的值，从而判断二叉树中是否存在节点和为指定值的路径。只需要去判断叶子节点的和是否为要求的值即可。

  • 具体思路如下图所示：



Pythton 代码： 
class Pair:
    def __init__(self,node, curSum):
        self.node = node
        self.curSum = curSum
        
class Solution:
    def hasPathSum(self , root: TreeNode, sum: int) -> bool:
        # write code here
        if root == None:
            return False
        nodeQueue = []
        pair = Pair(root, root.val)
        nodeQueue.append(pair)

        while nodeQueue:
            curPair = nodeQueue.pop(0)
            if curPair.node.left !=None:
                nodeQueue.append(Pair(curPair.node.left, curPair.curSum+curPair.
                  node.left.val))
            if curPair.node.right != None:
                nodeQueue.append(Pair(curPair.node.right, curPair.curSum +curPair.node.right.val))
            if curPair.node.left ==None and curPair.node.right == None:
                if sum  == curPair.curSum:
                    return True

  • 时间复杂度为O(n)O(n)，n为二叉树节点数，最差需要遍历所有节点。

  • 空间复杂度为O(n)O(n)，使用到了队列来记录节点，最差需要空间为n，即节点数。

参考资料：