扫二维码与项目经理沟通
我们在微信上24小时期待你的声音
解答本文疑问/技术咨询/运营咨询/技术建议/互联网交流
下面题目中的路径，定义有所延伸，在解法思路及时间空间复杂度上有所挑战。
437. Path Sum III
You are given a binary tree in which each node contains an integer value.
Find the number of paths that sum to a given value.
The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).
The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.
Example:
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
10
/ \
5 -3
/ \ \
3 2 11
/ \ \
3 -2 1
Return 3. The paths that sum to 8 are:
1. 5 -> 3
2. 5 -> 2 -> 1
3. -3 -> 11
题目解析：
此题的路径延伸至任一结点至其子孙结点的路径，解法一，速度将近1s，非常慢，但是写法简洁，思路也是最为直接的一种，对这棵树前序遍历，调用dfs函数，求从该结点起至任一子结点的路径和是否为sum。该方法效果低的原因就是大量重复遍历。
class Solution:
def pathSum(self, root: TreeNode, sum: int) -> int:
"""
:type root: TreeNode
:type sum: int
:rtype: int
"""
def dfs(node, sum):
return dfs(node.left, sum-node.val) + dfs(node.right, sum-node.val) + (sum == node.val) if node else 0
return dfs(root, sum) + self.pathSum(root.left, sum) + self.pathSum(root.right, sum) if root else 0
解法二，用非递归后序遍历的框架，stack存储所有父结点，sums列表存储的是以任一结点为起始的路径和(有点类似动态规划?)，因此sums的长度和stack一致，当sums中的任一数字与sum相等，都是一个满足要求的路径。在后序遍历的过程中，结点退栈，sums中对应的也退栈，并且每个数字减去该结点的值。该方法速度500ms，但是空间复杂度基本是top，beat 99.9%。
class Solution:
def pathSum(self, root: TreeNode, sum: int) -> int:
if not root:
return 0
stack = []
sums = []
f = 0
res = 0
p = root
while True:
while p:
stack.append(p)
sums.append(0)
for i in range(len(sums)):
sums[i] += p.val
if sums[i] == sum:
res += 1
p = p.left
pre = None
f = 1
while stack and f:
p = stack[-1]
if p.right == pre:
sums.pop()
for i in range(len(sums)):
sums[i] -= p.val
stack.pop()
pre = p
else:
p = p.right
f = 0
if not stack:
break
return res
明显时间复杂度上还有很多优化空间，我们看解法三，大佬所做，52ms，可谓相当可以了。细细揣摩，大思路上，同上一个解法，仍然是只遍历一次，避免重复，因此需要存储曾出现的路径和，这一解法引入了hashmap。鄙人的方法慢在sums列表的值，需要挨个加减以维持其作用，而sumMap作用相同，通过操作字典的键值对，解决了性能问题。参考这一思路，可以在上面非递归的框架下改写一番。
class Solution:
def pathSum(self, root: TreeNode, sum: int) -> int:
"""
:type root: TreeNode
:type sum: int
:rtype: int
"""
from collections import defaultdict
def helper(cur, sumSoFar):
nonlocal res, sumMap
sumSoFar += cur.val
if sumSoFar == sum:
res += 1 无锡看妇科的医院 http://www.ytsg120.cn
res += sumMap[sumSoFar - sum]
sumMap[sumSoFar] += 1
if cur.left:
helper(cur.left, sumSoFar)
if cur.right:
helper(cur.right, sumSoFar)
sumMap[sumSoFar] -= 1
if not root:
return 0
sumMap = defaultdict(int)
res = 0 if root.val != sum else 1
sumMap[root.val] = 1
if root.left:
helper(root.left, root.val)
if root.right:
helper(root.right, root.val)
return res
124. Binary Tree Maximum Path Sum
Given a non-empty binary tree, find the maximum path sum.
For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.
Example 1:
Input: [1,2,3]
1
/ \
2 3
Output: 6
Example 2:
Input: [-10,9,20,null,null,15,7]
-10
/ \
9 20
/ \
15 7
Output: 42
题目解析：
这道题在我看来，似乎是路径题目中的大boss。题目百思不得其解，最后还是看了其他人的写法，自己琢磨了一番，其实不同于其他路径问题。我们先看代码。
class Solution:
def maxPathSum(self, root: TreeNode) -> int:
max_sum = float("-inf")
def helper(node):
nonlocal max_sum
if not node:
return 0
lt_sum = helper(node.left)
rt_sum = helper(node.right)
local_sum = max(node.val, max(lt_sum, rt_sum) + node.val) # 1
max_sum = max(max_sum, max(local_sum, lt_sum + rt_sum + node.val)) # 2
return local_sum
helper(root)
return max_sum
首先，该题目的路径大有不同，不一定包括叶子结点，也不一定包括根结点，有可能是从左子到父到右子的路径。题目的结果，是一个全局变量;解题过程是一个普通的先序遍历，递归的过程中完成两件事：一是返回local_sum，是左或右子树大和，代码1判断是该结点值自己大，还是加上其左右子树之一的和大(只能选一个)，该局部值向上递归，相当于在求路径和的问题时，把这样的大问题分解为一个个小问题来解决;第二件事是更新max_sum，此时允许该结点值加上左右子树的大和，构成一个完整的路径，判断改值是不是大。
另外有需要云服务器可以了解下创新互联cdcxhl.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。
我们在微信上24小时期待你的声音
解答本文疑问/技术咨询/运营咨询/技术建议/互联网交流
微信二维码
移动版官网