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，此時允許該結點值加上左右子樹的最大和，構成一個完整的路徑，判斷改值是不是最大。