路径总和
一、题目描述
给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
说明: 叶子节点是指没有子节点的节点。
示例:
给定如下二叉树，以及目标和 sum = 22，
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。
二、解题思路 & 代码
2.1 DFS
首先是 DFS 解法，该解法的想法是一直向下找到叶子节点，如果到叶子节点时
sum == 0，说明找到了一条符合要求的路径。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def hasPathSum(self, root, sum):
""" :type root: TreeNode :type sum: int :rtype: bool """
if not root: return False
if not root.left and not root.right:
return sum == root.val
return self.hasPathSum(root.left, sum - root.val) or self.hasPathSum(root.right, sum - root.val)
复杂度分析
- 时间复杂度：O(N)，其中 N 是树的节点数。对每个节点访问一次。
- 空间复杂度：O(H)，其中 H 是树的高度。空间复杂度主要取决于递归时栈空间的开销，最坏情况下，树呈现链状，空间复杂度为 O(N)。平均情况下树的高度与节点数的对数正相关，空间复杂度为 O(logN)。
2.2 BFS
BFS 使用 队列 保存遍历到每个节点时的路径和，如果该节点恰好是叶子节点，并且 路径和 正好等于 sum，说明找到了解。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def hasPathSum(self, root: TreeNode, sum: int) -> bool:
if not root:
return False
que = collections.deque()
que.append((root, root.val))
while que:
node, path = que.popleft()
if not node.left and not node.right and path == sum:
return True
if node.left:
que.append((node.left, path + node.left.val))
if node.right:
que.append((node.right, path + node.right.val))
return False
复杂度分析
- 时间复杂度：O(N)，其中 N 是树的节点数。对每个节点访问一次。
- 空间复杂度：O(N)，其中 N 是树的节点数。空间复杂度主要取决于队列的开销，队列中的元素个数不会超过树的节点数。
2.3 栈
除了上面的 队列 解法以外，也可以使用 栈，同时保存节点和到这个节点的路径和。但是这个解法已经不是 BFS。因为会优先访问 后进来 的节点，导致会把根节点的右子树访问结束之后，才访问左子树。
可能会有朋友好奇很少见到这种写法，为什么代码可行？答案是：栈中同时保存了 (节点，路径和)，也就是说只要能把所有的节点访问一遍，那么就一定能找到正确的结果。无论是用 队列 还是 栈，都是一种 树的遍历 方式，只不过访问顺序有所有不同罢了。
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def hasPathSum(self, root, sum):
""" :type root: TreeNode :type sum: int :rtype: bool """
if not root:
return False
stack = []
stack.append((root, root.val))
while stack:
node, path = stack.pop()
if not node.left and not node.right and path == sum:
return True
if node.left:
stack.append((node.left, path + node.left.val))
if node.right:
stack.append((node.right, path + node.right.val))
return False
#######################################################################################################################################################################################################
路径总和 II
一、题目描述
给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
说明: 叶子节点是指没有子节点的节点。
示例:
给定如下二叉树，以及目标和 sum = 22，
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
返回:
[
[5,4,11,2],
[5,8,4,5]
]
二、解题思路 & 代码
2.1 递归
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def pathSum(self, root: TreeNode, sum_: int) -> List[List[int]]:
def helper(root, tmp, sum_):
if not root:
return
if not root.left and not root.right and sum_ - root.val == 0:
tmp += [root.val]
res.append(tmp)
helper(root.left, tmp + [root.val], sum_ - root.val)
helper(root.right, tmp + [root.val], sum_ - root.val)
res = []
helper(root, [], sum_)
return res
2.2 非递归
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def pathSum(self, root: TreeNode, sum_: int) -> List[List[int]]:
if not root: return []
stack = [([root.val], root)]
res = []
while stack:
tmp, node = stack.pop()
if not node.right and not node.left and sum(tmp) == sum_:
res.append(tmp)
if node.right:
stack.append((tmp + [node.right.val], node.right))
if node.left:
stack.append((tmp + [node.left.val], node.left))
return res
###################################################################################################################################################################################################
路径总和 III
一、题目描述
给定一个二叉树，它的每个结点都存放着一个整数值。
找出路径和等于给定数值的路径总数。
路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。
示例：
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
10
/ \
5 -3
/ \ \
3 2 11
/ \ \
3 -2 1
返回 3。和等于 8 的路径有:
1. 5 -> 3
2. 5 -> 2 -> 1
3. -3 -> 11
二、解题思路 & 代码
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
# 展开版，易理解
class Solution:
def pathSum(self, root: TreeNode, sum: int) -> int:
def dfs(root, sumlist):
if root is None:
return 0
sumlist = [num+root.val for num in sumlist]
sumlist.append(root.val)
count = 0
for num in sumlist:
if num == sum:
count += 1
# count = sumlist.count(sum)
return count + dfs(root.left, sumlist) + dfs(root.right, sumlist)
return dfs(root, [])
京公网安备 11010502036488号