【完虐算法】 非自頂向下類別題目復盤專題

大家好，我是Johngo！

這篇文章是「講透樹」系列的第 4 篇文章，也是「樹」專題中非自頂向下這類題目的一個復盤總結。

前 3 講的鏈接地址在這里了：

講透樹1 | 樹的基礎遍歷專題 https://mp.weixin.qq.com/s/nTB41DvE7bfrT7_rW_gfXw

講透樹2 | 樹的遍歷復盤專題 https://mp.weixin.qq.com/s/MkCF5TaR1JD3F3E2MKlgVw

講透樹3 | 自頂向下類別題目復盤專題 https://mp.weixin.qq.com/s/9U4P5zZIFppiJO_XK2QFDA

不同的類型已經都進行了各自的總結，相信在后面記憶不太清晰的時候，返回頭來看看，這些文檔又會和思維激起靈魂碰撞！

階段說明

一起刷題的小伙伴們，復盤還是要嘮叨一句，記錄思路，在記錄的過程中，又一次深刻體會！比如說

相信在后面記憶不太清晰的時候，返回頭來看看，這些文檔又會和思維激起靈魂碰撞！

直觀的先看看本文的所處的一個進度

相比較于「自頂向下」的題目，「非自頂向下」的題目相比較下來不太適合用 BFS 來解決，非常適合于用 DFS 來解決。而且相較于「自頂向下」的題目，「非自頂向下」的題目難度會大一點。

關于 BFS 的解題思路對于「自頂向下」這類型題目是非常友好的，思路清晰。可查看這里https://mp.weixin.qq.com/s/9U4P5zZIFppiJO_XK2QFDA。

本篇文章涉及到的題目

687.最長同值路徑：https://leetcode-cn.com/problems/longest-univalue-path/

124.二叉樹中的最大路徑和：https://leetcode-cn.com/problems/binary-tree-maximum-path-sum

543.二叉樹的直徑：https://leetcode-cn.com/problems/diameter-of-binary-tree

652.尋找重復的子樹：https://leetcode-cn.com/problems/find-duplicate-subtrees/

236.二叉樹的最近公共祖先：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree

235.二叉搜索樹的最近公共祖先：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree

DFS 解題思路

本篇著重說「非自頂向下」的思路以及涉及到的 LeetCode 題目。

在這里總結一句，其實就是下面三種基礎遞歸遍歷的變形，這個變形來源于題目的要求，但本質都是遞歸遍歷。

這里我再一次把三種二叉樹遞歸的代碼貼出來：

二叉樹的先序遍歷

def pre_order_traverse(self, head): if head is None: return print(head.value, end=" ") self.pre_order_traverse(head.left) self.pre_order_traverse(head.right)

二叉樹的中序遍歷

def in_order_traverse(self, head): if head is None: return self.in_order_traverse(head.left) print(head.value, end=" ") self.in_order_traverse(head.right)

二叉樹的后續遍歷

def post_order_traverse(self, head): if head is None: return self.post_order_traverse(head.left) self.post_order_traverse(head.right) print(head.value, end=" ")

令人整潔的舒服…

令人難以理解的不舒服…

對的，就是這種整潔的代碼，在處理起二叉樹的問題來，著實是游刃有余的。

案例剖析

LeetCode687.最長同值路徑

題目鏈接：https://leetcode-cn.com/problems/longest-univalue-path/

GitHub解答：https://github.com/xiaozhutec/share_leetcode/blob/master/樹/687.最長同值路徑.py

這就是一個后續的遞歸遍歷，后續遞歸遍歷完，不進行結點的打印，而是進行結點值和相關孩子結點的比對判斷：

def longestUnivaluePath_dfs(self, root): self.length = 0 def dfs(root): if not root: return 0 left_len = dfs(root.left) right_len = dfs(root.right) left_tag = right_tag = 0 if root.left and root.left.val == root.val: left_tag = left_len + 1 if root.right and root.right.val == root.val: right_tag = right_len + 1 # max(最大長度, 左子樹最大長度+右子樹最大長度) self.length = max(self.length, left_tag + right_tag) return max(left_tag, right_tag) dfs(root) return self.length

看到了吧，其實就是在left_len = dfs(root.left) 和 right_len = dfs(root.right) 之后，進行當前結點和左右孩子結點的結點值比對，如果相同了，很顯然是 +1。

另外，就題論題。

下面會介紹一種很重要的思路，在很多題目中都會遇到。

這個題目有很關鍵的一點是self.length = max(self.length, left_tag + right_tag)，由于題目不要求一定經過根結點。那么，此時如果左孩子的結點值和根結點的結點值以及右孩子的結點值和根結點的結點值都相同，此時會是下面的一種情況。

談論紅色框內的結點：

灰色結點的左孩子length=1，灰色結點的右孩子length=0；

再往上層看，灰色結點 5 的左孩子也是 5，那么left_tag=2，灰色結點 5 的右孩子也是 5，那么right_tag=1；

所以，length = max(length, left_tag + right_tag)，那么，得到的結果是length=3，也就是黑色所示的粗邊。

以上，利用后續遍歷的遞歸思想，就可以把問題解決了！

強調：上面的思路經常會遇到，很重要！

再看一個例子：

LeetCode124.二叉樹中的最大路徑和

題目鏈接：https://leetcode-cn.com/problems/binary-tree-maximum-path-sum

GitHub解答：https://github.com/xiaozhutec/share_leetcode/blob/master/樹/124.二叉樹中的最大路徑和.py

從二叉樹中找出一個最大的路徑，就是找到一個連續結點值最大的一個路徑。

可以參考上一個題目的思路，依然采用后續遍歷的思路，進行解決。

def maxPathSum(self, root): self.length = float("-inf") def dfs(root): if not root: return 0 left_len = max(dfs(root.left), 0) # 只有貢獻值大于 0 的，才會選取對應的子結構 right_len = max(dfs(root.right), 0) inner_max = left_len + root.val + right_len self.length = max(self.length, inner_max) # 計算當前結點所在子樹的最大路徑 return max(left_len, right_len) + root.val # 返回當前結點左右子結構的最大路徑 dfs(root) return self.length

思路依然還是比較輕松的吧，后續遍歷的典型變形。

看這句self.length = max(self.length, inner_max)，是不是和上一題異曲同工，也是比較上一層遞歸的 length 和本層中 inner_max作比較，找出最大值。

兩點注意

每次遞歸，需要計算 length 的值，以保證每次遞歸得到最大路徑和

每次遞歸的返回值一定是左子樹和右子樹中的最大值+當前結點值

再來看一道題目：

LeetCode543.二叉樹的直徑

題目鏈接：https://leetcode-cn.com/problems/diameter-of-binary-tree

GitHub解答：https://github.com/xiaozhutec/share_leetcode/blob/master/樹/543.二叉樹的直徑.py

題目要求返回一顆二叉樹的直徑，其實還是一個后續遞歸遍歷。

依然還是采用上述「LeetCode687」中介紹的重要思路進行求解。

def diameterOfBinaryTree(self, root): self.path_length = 0 def dfs(root): if not root: return 0 left_len = dfs(root.left) right_len = dfs(root.right) left_tag = right_tag = 0 if root.left: left_tag = left_len + 1 if root.right: right_tag = right_len + 1 self.path_length = max(self.path_length, left_tag + right_tag) return max(left_tag, right_tag) dfs(root) return self.path_length

依然是后續遍歷，遞歸調用后，采用max(self.path_length, left_tag + right_tag)，比較上一層返回的 length和左右子樹中的最大值。

依然是兩點：

每次遞歸計算 length 的值，找當前結點最長路徑

返回左右子樹的最大路徑長度

上面說了三個題目，大致思路都相同，不同的是一個題目計算路徑和、兩個題目是計算路徑長度。

比較重要的那個點，在「LeetCode687」中介紹的重要思路，這個是最重要的一環，務必理解加以運用！

見得太多，用的也太多！

最后咱們再看兩個題目：

LeetCode236.二叉樹的最近公共祖先

題目鏈接：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree

GitHub解答：https://github.com/xiaozhutec/share_leetcode/blob/master/樹/236.二叉樹的最近公共祖先.py

這個是給定兩個結點，求解他們的最近公共祖先，也是一個遞歸的問題。

def lowestCommonAncestor(self, root, p, q): if not root or root == p or root == q: return root left = self.lowestCommonAncestor(root.left, p, q) right = self.lowestCommonAncestor(root.right, p, q) if not left: return right if not right: return left return root

其實說白了還是遞歸的思路進行求解，不過這里需要注意四種情況：

1.無左孩子 and 無右孩子，直接返回根結點

2.無左孩子 and 有右孩子，直接返回根結點

3.有左孩子 and 無右孩子，直接返回根結點

4.有左孩子 and 有右孩子，繼續遞歸遍歷

所以，還是遞歸的變形進行解決，唯一有一點就是需要深入思考，深入體會。

LeetCode235.二叉搜索樹的最近公共祖先

題目鏈接：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree

GitHub解答：https://github.com/xiaozhutec/share_leetcode/blob/master/樹/235.二叉搜索樹的最近公共祖先.py

這個題目是上一個題目的變形，難度降低，因為要考察的二叉樹由一般結構變為了二叉搜索樹。

因此，利用搜索二叉樹的性質，稍進行判斷就可以解決。

def lowestCommonAncestor(self, root, p, q): if p.val < root.val and q.val < root.val: return self.lowestCommonAncestor(root.left, p, q) if p.val > root.val and q.val > root.val: return self.lowestCommonAncestor(root.right, p, q) return root.val

是不是很簡單整潔的代碼。

第一個if，就是如果p和q都小于當前結點，那么直接到左子樹進行遞歸調用；

第二個if，就是如果p和q都大于當前結點，那么直接到右子樹進行遞歸調用；

如果都不滿足，即就是所需要的答案。

想想看，是不是？利用搜索二叉樹的結構，其實思路很清晰簡單。

好了，「樹」這一階段的刷題已經進入尾聲，但我理解在第一輪刷題完畢之后，還會繼續回來重新來過。

下一階段就到了「動態規劃」的一個刷題時間窗口了，遞歸和動態規劃都是出了名的比較難學，但是它們的思想深入貫徹整個算法的各個節點。所以，堅持把這幾部分內容都進行一個總結，讓大家把思路逐漸清晰起來！

代碼和本文的文檔都在 https://github.com/xiaozhutec/share_leetcode，需要的小伙伴可以自行下載代碼運行跑起來！方便的話給個 star。謝過大家！

二叉樹 數據結構

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。