0112._path_sum.md

Navigation

• Navigation
• Links:
• Tags
• Solution 1 DFS，递归
• Solution 2 DFS，自定义栈，迭代
• Solution 3 BFS，队列
• 总结

Links:

1. https://leetcode.com/problems/path-sum/
2. https://leetcode-cn.com/problems/path-sum/

Tags

1. 树
2. 深度优先

Solution 1 DFS，递归

如果不是叶子节点，则递归下去。 如果是叶子节点，则判断sum当前是否为0.

class Solution:
    """
        时间复杂度: 每个节点访问一次，所以是O(N)
        空间复杂度: 最坏是非平衡数，递归会调用N次（树的高度），因此栈的空间开销为O(N)。\
            在最好的情况下，树是平衡的，O(log(N)).
                  
    """
    def hasPathSum(self, root, total):
        if not root:
            return False

        total -= root.val

        if not root.left and not root.right:
            return total == 0

        return self.hasPathSum(root.left, total) or self.hasPathSum(root.right, total)

Solution 2 DFS，自定义栈，迭代

class Solution:
    """
        时间复杂度和空间复杂度和Solution 1 一样
    """
    def hasPathSum(self, root, total):
        if not root:
            return False

        stack = [(root, total - root.val)]

        while stack:    # 先序遍历
            node, curr_sum = stack.pop()

            if not node.left and not node.right:    # 叶子节点
                if curr_sum == 0:
                    return True

            if node.right:
                stack.append((node.right, curr_sum - node.right.val))
            
            if node.left:
                stack.append((node.left, curr_sum - node.left.val))

        return False

Solution 3 BFS，队列

from collections import deque

class Solution:
    def hasPathSum(self, root, total):
        deq = deque()

        if root:
            deq.append((root, total - root.val))

        while deq:
            node, curr_sum = deq.popleft()

            if not node.left and not node.right:    # 叶子节点
                if curr_sum == 0:
                    return True

            if node.right:
                deq.append((node.right, curr_sum - node.right.val))

            if node.left:
                deq.append((node.left, curr_sum - node.left.val))

        return False                  

总结

根据题目描述，“判断该树中是否存在根节点到叶子节点的路径”。所以一定要到达叶子节点。 这样的话，一般来说，DFS比BFS更快更适合。因为BFS要计算完这一层的节点才到下一层，到达叶子节点的速度比DFS慢。