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