python7.4.2二叉树路径问题及LeetCode题目解析

下面题目中的路径，定义有所延伸，在解法思路及时间空间复杂度上有所挑战。

创新互联专业为企业提供光明网站建设、光明做网站、光明网站设计、光明网站制作等企业网站建设、网页设计与制作、光明企业网站模板建站服务，十载光明做网站经验，不只是建网站，更提供有价值的思路和整体网络服务。

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，此时允许该结点值加上左右子树的最大和，构成一个完整的路径，判断改值是不是最大。