題目傳送門：力扣?leetcode-cn.com

昨天下午突然接到某公司算法崗面試，問到的算法題。

題目描述：

給定一個非空二叉樹，返回其最大路徑和。

本題中，路徑被定義為一條從樹中任意節點出發，達到任意節點的序列。該路徑至少包含一個節點，且不一定經過根節點。

可以將這顆二叉樹看作為聯通圖，每個節點都有一個數值，輸出最大的無環路徑(每個點只能經過一次)。

被問到這題還是很慌的，由于最近幾天才在找工，題也沒刷多少，這題我都沒做過(太菜了)，搞的我當場直接沉默了一分鐘有余。但我隨后意識到二叉樹這一數據結構還是很特殊的，一般應該遞歸地計算，那么怎么遞歸呢？

思路

如果構造一個遞歸地遍歷二叉樹的函數，那么在對于每一個葉子節點而言，顯然應該是返回葉子節點自己的值，意義是葉子節點自己就是當前狀態的最大路徑。所以在這里，狀態可以視作為：經過當前節點的最大路徑值。但是對于非葉子節點而言情況復雜一些。首先，假如根據我們先前的定義，每個節點都是返回經過當前狀態的最大路徑的話，其父節點的最大路徑值不一定需要這個最大路徑，因為可能這個最大路徑是包括了子節點左右兩棵子樹，這樣就不滿足路徑的定義，即：每個節點只能經過一次。在這里糾正了前面的“經過當前節點的最大路徑值“的推斷(面試的時候我一開始也是這樣犯錯的)。

那么為了使得狀態的返回值對于其父節點而言是有效的，狀態的意義應該調整為，從當前節點出發，沿著一個子樹搜索得到的最大路徑，這條路徑保證一個終點是當前節點。這樣，這個狀態值才可以為上一個節點所用。那么現在又出現一個問題：現在最大路徑是什么呢，因為這才是我們要求的答案。我們依舊考慮其中的任意一個節點狀態，如果我們知道了末端在左子樹，起點在當前節點的最長路徑，同時也知道了末端在右子樹，起點在當前節點的最長路徑，那么兩者合并就是經過當前節點的最長路徑。故我們只需要用一個全局變量記錄比較即可，因為最后返回值必須還是其中一支最大路徑，不一定經過根結點。由于節點的值可能為負數，因此還需要加上0比較，其意義是如果有一個子樹的返回值為負數，就不需要考慮這條路徑了，因為這會帶來負面影響。

轉移方程:

邊界情況為無子樹：

最大路徑的值：

最終答案：

代碼

# Definition for a binary tree node.

# class TreeNode:

# def __init__(self, x):

# self.val = x

# self.left = None

# self.right = None

class Solution:

def dfs(self,node: TreeNode) ->int :

if node.left == None:

lm = 0

else:

lm = self.dfs(node.left)

if node.right == None:

rm = 0

else:

rm = self.dfs(node.right)

if max(lm+rm,0,rm,lm)+node.val > self.m:

self.m = max(lm+rm,0,rm,lm)+node.val

return max(lm,0,rm)+node.val

def maxPathSum(self, root: TreeNode) -> int:

self.m = -0xFFFFFFFF

self.dfs(root)

return self.m

備注：這是一道樹形DP的經典例題，還是要多刷題啊，要不然面試差點翻車。

總結

以上是生活随笔為你收集整理的二叉树最大路径和 python_[面试题]二叉树中最大路径和的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。