python7.4.2二叉樹路徑問題及LeetCode題目解析-創(chuàng)新互聯(lián)
下面題目中的路徑，定義有所延伸，在解法思路及時(shí)間空間復(fù)雜度上有所挑戰(zhàn)。
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
題目解析：
此題的路徑延伸至任一結(jié)點(diǎn)至其子孫結(jié)點(diǎn)的路徑，解法一，速度將近1s，非常慢，但是寫法簡潔，思路也是最為直接的一種，對這棵樹前序遍歷，調(diào)用dfs函數(shù)，求從該結(jié)點(diǎn)起至任一子結(jié)點(diǎn)的路徑和是否為sum。該方法效果低的原因就是大量重復(fù)遍歷。
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存儲所有父結(jié)點(diǎn)，sums列表存儲的是以任一結(jié)點(diǎn)為起始的路徑和(有點(diǎn)類似動(dòng)態(tài)規(guī)劃?)，因此sums的長度和stack一致，當(dāng)sums中的任一數(shù)字與sum相等，都是一個(gè)滿足要求的路徑。在后序遍歷的過程中，結(jié)點(diǎn)退棧，sums中對應(yīng)的也退棧，并且每個(gè)數(shù)字減去該結(jié)點(diǎn)的值。該方法速度500ms，但是空間復(fù)雜度基本是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
明顯時(shí)間復(fù)雜度上還有很多優(yōu)化空間，我們看解法三，大佬所做，52ms，可謂相當(dāng)可以了。細(xì)細(xì)揣摩，大思路上，同上一個(gè)解法，仍然是只遍歷一次，避免重復(fù)，因此需要存儲曾出現(xiàn)的路徑和，這一解法引入了hashmap。鄙人的方法慢在sums列表的值，需要挨個(gè)加減以維持其作用，而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 無錫看婦科的醫(yī)院 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。題目百思不得其解，最后還是看了其他人的寫法，自己琢磨了一番，其實(shí)不同于其他路徑問題。我們先看代碼。
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
首先，該題目的路徑大有不同，不一定包括葉子結(jié)點(diǎn)，也不一定包括根結(jié)點(diǎn)，有可能是從左子到父到右子的路徑。題目的結(jié)果，是一個(gè)全局變量;解題過程是一個(gè)普通的先序遍歷，遞歸的過程中完成兩件事：一是返回local_sum，是左或右子樹大和，代碼1判斷是該結(jié)點(diǎn)值自己大，還是加上其左右子樹之一的和大(只能選一個(gè))，該局部值向上遞歸，相當(dāng)于在求路徑和的問題時(shí)，把這樣的大問題分解為一個(gè)個(gè)小問題來解決;第二件事是更新max_sum，此時(shí)允許該結(jié)點(diǎn)值加上左右子樹的大和，構(gòu)成一個(gè)完整的路徑，判斷改值是不是大。
另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)cdcxhl.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。
分享名稱：python7.4.2二叉樹路徑問題及LeetCode題目解析-創(chuàng)新互聯(lián)
鏈接地址：http://m.jiaotiyi.com/article/cdpcdi.html