一、112. 路径总和
实际就是实现了深度优先搜索（DFS）
# 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
if not root.left and not root.right and sum - root.val == 0:
return True
return self.hasPathSum(root.left, sum - root.val) or self.hasPathSum(root.right, sum - root.val)
此处使用中序遍历
class Solution:
# 深度优先搜索(DFS)
def hasPathSum(self, root: TreeNode, sum: int) -> bool:
if not root: return False
que = []
queSum = []
node = root
curSum = 0
while len(que) > 0 or node:
# 将该节点的左路径全部压入栈中
while node:
que.append(node)
curSum += node.val
queSum.append(curSum)
node = node.left
node = que.pop()
curSum = queSum.pop()
# 叶子节点，路径和满足条件
if curSum == sum and not node.left and not node.right:
return True
# 考虑右节点
node = node.right
return False
class Solution:
# 深度优先搜索(DFS)
def hasPathSum(self, root: TreeNode, sum: int) -> bool:
if not root: return False
que = []
node = root
pre = None
curSum = 0
# 后序遍历, 先遍历左子树， 再遍历右子树， 最后遍历根节点
while len(que) > 0 or node:
# 将该节点的左路径全部压入栈中
while node:
que.append(node)
curSum += node.val
node = node.left
node = que[-1]
# print(node.val, curSum, node.left, node.right)
# 叶子节点，路径和满足条件
if curSum == sum and not node.left and not node.right:
return True
# 考虑右节点
if not node.right or pre == node.right:
pop = que.pop()
curSum -= pop.val
pre = node
node = None
else:
node = node.right
return False
class Solution:
# 广度优先搜索(BFS)
def hasPathSum(self, root: TreeNode, sum: int) -> bool:
if not root: return False
que = []
queSum = []
que.append(root)
queSum.append(root.val)
while len(que) > 0:
queSize = len(que)
# 层次遍历
for i in range(queSize):
node = que.pop(0) # 模拟队首弹出
curSum = queSum.pop(0) # 模拟队首弹出
# 是叶子节点， 且路径和满足条件
if not node.left and not node.right and curSum == sum : return True
# 当前节点 和 累计和 压入队列
if node.left:
que.append(node.left)
queSum.append(node.left.val + curSum)
if node.right:
que.append(node.right)
queSum.append(node.right.val + curSum)
return False
层次遍历，使用队列存储待遍历的节点，另一个队列存储对应的路径，当遇到叶子节点，将路径存入列表中。（BFS）
class Solution:
def binaryTreePaths(self, root: TreeNode) -> List[str]:
if not root:
return None
que = []
que.append(root)
queStr = []
queStr.append(str(root.val))
ret = []
while len(que) > 0:
queSize = len(que)
for i in range(queSize):
# 模拟队列
cur = que.pop(0)
curStr = queStr.pop(0)
# print(cur.val, curStr, queSize)
# 叶子节点
if not cur.left and not cur.right:
ret.append(curStr)
continue
if cur.left:
que.append(cur.left)
queStr.append(curStr + "->" + str(cur.left.val))
if cur.right:
que.append(cur.right)
queStr.append(curStr + "->" + str(cur.right.val))
return ret
class Solution:
def binaryTreePaths(self, root: TreeNode) -> List[str]:
if not root:
return None
retPaths = []
self.nodePath(root, str(root.val), retPaths)
return retPaths
# 递归
def nodePath(self, node: TreeNode, path: str, retPaths: List[str]) -> None:
# 叶子节点
if not node.left and not node.right:
retPaths.append(path)
if node.left:
leftPath = path + '->' + str(node.left.val)
self.nodePath(node.left, leftPath, retPaths)
if node.right:
rightPath = path + '->' + str(node.right.val)
self.nodePath(node.right, rightPath, retPaths)
class Solution:
def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
if not root:
return []
retPaths = []
self.nodePath(root, [root.val], retPaths, sum-root.val)
return retPaths
# 递归， 从上向下
def nodePath(self, node: TreeNode, path: List[int], paths: List[List[int]], sum: int) -> None:
if not node.left and not node.right:
if sum == 0:
paths.append(path)
else:
if node.left:
leftPath= path[:]
leftPath.append(node.left.val)
self.nodePath(node.left, leftPath, paths, sum-node.left.val)
if node.right:
rightPath = path[:]
rightPath.append(node.right.val)
self.nodePath(node.right, rightPath, paths, sum-node.right.val)
class Solution:
def pathSum(self, root: TreeNode, sum: int) -> int:
if not root: return 0
return self.nodeSum(root, sum) + self.pathSum(root.left, sum) + self.pathSum(root.right, sum)
# 计算某个节点的路径和
def nodeSum(self, root: TreeNode, _sum: int) -> int:
if not root: return 0
_sum -= root.val
count = 1 if _sum == 0 else 0
return count + self.nodeSum(root.left, _sum) + self.nodeSum(root.right, _sum)
采取了类似于数组的前n项和的思路，比如sum[4] == sum[1]，那么1到4之间的和肯定为0
对于树的话，采取DFS加回溯，每次访问到一个节点，把该节点加入到当前的pathSum中 然后判断是否存在一个之前的前n项和，其值等于pathSum与sum之差 如果有，就说明现在的前n项和，减去之前的前n项和，等于sum，那么也就是说，这两个点之间的路径和，就是sum
最后要注意的是，记得回溯，把路径和弹出去
class Solution:
def pathSum(self, root: TreeNode, sum: int) -> int:
if not root: return 0
return self.nodeSum(root, sum, 0)
def __init__(self) -> None:
self.map = {0:1}
# 计算某个节点的路径和
def nodeSum(self, root: TreeNode, target: int, pathSum: int) -> int:
if not root: return 0
count = 0
pathSum += root.val
preSum = pathSum-target
if preSum in self.map:
count = self.map[preSum]
if pathSum not in self.map:
self.map[pathSum] = 0
self.map[pathSum] += 1
count = self.nodeSum(root.left, target, pathSum) + self.nodeSum(root.right, target, pathSum) + count
# 回溯
self.map[pathSum] -= 1
return count
在穿过左子树，根节点，右子树的一条路径中 
最长的路径可能有三种情况：
- 1.在左子树内部
- 2.在右子树内部
- 3.在穿过左子树，根节点，右子树的一条路径中
class Solution:
def longestUnivaluePath(self, root: TreeNode) -> int:
if not root: return 0
self.__dfs(root, root.val)
return self.maxLen
def __init__(self) -> None:
self.maxLen = 0
def __dfs(self, root: TreeNode, preVal: int) -> int:
if not root: return 0
if preVal == root.val:
left = self.__dfs(root.left, root.val)
right = self.__dfs(root.right, root.val)
self.maxLen = max(left + right, self.maxLen)
return max(left, right) + 1
else:
self.__dfs(root, root.val)
return 0
与 687. 最长同值路径类似。
6.1、题目描述
class Solution:
def maxPathSum(self, root: TreeNode) -> int:
self.__dfs(root)
return self.maxSum
def __init__(self) -> None:
self.maxSum = float('-inf')
def __dfs(self, root: TreeNode) -> int:
if not root: return 0
# 另外结点有可能是负值，最大和肯定就要想办法舍弃负值(max(0, x))
left = max(self.__dfs(root.left), 0)
right = max(self.__dfs(root.right), 0)
self.maxSum = max(self.maxSum, left+right+root.val)
return max(left, right) + root.val
class Solution:
def sumNumbers(self, root: TreeNode) -> int:
self.__dfs(root, 0)
return self._sum
def __init__(self) -> None:
self._sum = 0
def __dfs(self, root: TreeNode, pSum) -> int:
if not root: return 0
# 叶子节点
if not root.left and not root.right:
self._sum += 10*pSum + root.val
# 将父节点的值向下传递
if root.left:
self.__dfs(root.left, 10*pSum+root.val)
if root.right:
self.__dfs(root.right, 10*pSum+root.val)
class Solution:
def sumNumbers(self, root: TreeNode) -> int:
return self.__dfs(root, 0)
def __dfs(self, root: TreeNode, pSum) -> int:
if not root: return 0
curSum = 10*pSum + root.val
# 叶子节点
if not root.left and not root.right:
return curSum
ans = 0
# 将父节点的值向下传递
if root.left:
ans += self.__dfs(root.left, curSum)
if root.right:
ans += self.__dfs(root.right, curSum)
return ans
class Solution:
def sumNumbers(self, root: TreeNode) -> int:
if not root: return 0
_sum = 0
# 双队列，记录子节点，以及父节点的累计数值
nodeStack = [root]
numStack = [0]
while nodeStack:
# 父节点
curNode = nodeStack.pop(0)
curSum = 10*numStack.pop(0) + curNode.val
if not curNode.left and not curNode.right:
_sum += curSum
if curNode.left:
# 当前节点
nodeStack.append(curNode.left)
# 父节点的累计数值
numStack.append(curSum)
if curNode.right:
nodeStack.append(curNode.right)
numStack.append(curSum)
return _sum
class Solution:
def sumNumbers(self, root: TreeNode) -> int:
if not root: return 0
_sum = 0
nodeStack = [root]
numStack = [0]
while nodeStack:
for i in range(len(nodeStack)):
# 父节点
curNode = nodeStack.pop(0)
curSum = 10*numStack.pop(0) + curNode.val
if not curNode.left and not curNode.right:
_sum += curSum
if curNode.left:
nodeStack.append(curNode.left)
numStack.append(curSum)
if curNode.right:
nodeStack.append(curNode.right)
numStack.append(curSum)
return _sum
本题和129. 求根到叶子节点数字之和类似，只是129时比较数值大小，本题比较字典顺序
8.2.1、递归
class Solution:
def smallestFromLeaf(self, root: TreeNode) -> str:
self.__dfs(root, '')
return self.path
def __init__(self) -> None:
self.path = None
def __dfs(self, root: TreeNode, path: str) -> None:
if not root: return 0
# 叶子节点
if not root.left and not root.right:
s = chr(97+root.val) + path
if not self.path:
self.path = s
self.path = min(s, self.path)
# 将父节点的值向下传递
if root.left:
self.__dfs(root.left, chr(97+root.val) + path)
if root.right:
self.__dfs(root.right, chr(97+root.val) + path)
