1鞭缭、為何要從樹下手
回溯剖膳、分治、動態(tài)規(guī)劃岭辣，在刷了這么多題之后的體會就是其實都是樹的遍歷吱晒，大多數(shù)算法與樹都脫不了干系，在東哥的指引下沦童，開始樹的模板總結(jié)：
2仑濒、樹的遍歷的框架特點
# 所謂的樹的遍歷的幾行破代碼
def find_next(root):
if xxx:
return
# 前序遍歷
do_some()
find_next(root.left)
# 中序遍歷
do_some()
find_next(root.right)
# 后序遍歷
do_some()
3叹话、樹框架的經(jīng)典案例
東哥舉了兩個典型的例子，雖然直觀上沒有聯(lián)系墩瞳，但都暗藏玄機驼壶，如下
3.1快速排序
簡單概要一下快排的精髓，從當前需要排序的數(shù)組nums中取一個截斷點(取數(shù)組第一個也好喉酌，隨機取也好)热凹，這個截斷點的作用就是分割數(shù)組，小于該點的放前面泪电，大于該點的放后面般妙，便產(chǎn)生左右兩個子數(shù)組，之后對左右數(shù)組遞歸執(zhí)行上述邏輯相速，當數(shù)組的size不足1時則停止碟渺。
# 快速排序偽代碼
def quick_sort(nums, l, r):
if r-l < 1:return
node = get_node(nums, l, r)
quick_sort(nums, l, node-1)
quick_sort(nums, node+1, r)
妥妥的前序遍歷的節(jié)奏，先找根突诬，再依次處理左右節(jié)點苫拍，偽代碼不過癮，上干貨
# 圖方便用了費內(nèi)存的寫法攒霹，可以試試在原數(shù)組上修改
def quick_sort(nums):
if len(nums) < 2:
return nums
else:
node = nums[0]
left_nums = [i for i in list[1:] if i<=node]
right_nums = [i for i in list[1:] if i > node]
return quick_sort(left_nums)+[node]+quick_sort(right_nums)
3.2歸并排序
同樣簡單概括一下歸并排序的精髓怯疤，其實也就是所謂的分治思想，把原有數(shù)組一分為二催束，分別排序集峦，最后再合并，遞歸則體現(xiàn)在分別排序里抠刺，分治的思想體現(xiàn)在塔淤，把問題設(shè)計成重復子問題，我要排一個大的速妖，只要排兩個小的高蜂，最終通過后續(xù)遍歷的回溯特性依次把小的數(shù)組，組裝起來復原成初始要求的大數(shù)組罕容。
提煉一下：
以我的理解串一下就是后續(xù)遍歷這種遞歸模式备恤，易構(gòu)成回溯的特性，從而能實現(xiàn)利用分治思想設(shè)計的解決方案锦秒，往后提前拓展一下可以體會到哈雏，遞歸可以實現(xiàn)逆向分治(自上而下的拆解)歌逢，而動態(tài)規(guī)劃則是分治的正向體現(xiàn)(自下而上的組裝)栖疑。
# 歸并排序偽代碼
def merge_sort(nums, l, r):
if r-l <=1:return
middle = (left+right) >> 1
merge_sort(nums, left, middle)
merge_sort(nums, middle+1, right)
merge(nums, left, middle, right)
干貨
def merge_sort(nums):
if len(nums) <= 1:
return nums
mid = len(nums) >> 1
left = merge_sort(nums[:mid])
right = merge_sort(nums[mid:])
return merge(left, right)
def merge(left, right):
result = []
i =j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result += left[i:]
result += right[j:]
return result
4预麸、寫法對比
隨便舉一個刷題的例子，每次寫遞歸總覺的自己寫的不優(yōu)美，這是為啥呢沉噩？
個人覺得這和我們平常的思維方式有關(guān)捺宗，比如這題路徑總和II我寫出了如下兩種遞歸解法：
遞歸1：
class Solution:
def pathSum(self, root: TreeNode, target: int) -> List[List[int]]:
if not root:
return []
ans = []
path = [root.val]
def dfs(node):
if not (node.left or node.right):
if sum(path) == target:
ans.append(path.copy())
return
if node.left:
path.append(node.left.val)
dfs(node.left)
path.pop()
if node.right:
path.append(node.right.val)
dfs(node.right)
path.pop()
dfs(root)
return ans
遞歸2：
class Solution:
def pathSum(self, root: TreeNode, target: int) -> List[List[int]]:
ans = []
path = []
def dfs(node):
# 退出條件
if not node:
return
# 處理當前節(jié)點
path.append(node.val)
if not (node.left or node.right):
if sum(path) == target:
ans.append(path.copy())
# 進入下層
dfs(node.left)
dfs(node.right)
# 清理當前節(jié)點
path.pop()
dfs(root)
return ans
遞歸2的方法是不是比第一種要好很多呢，代碼看著思路也清晰川蒙，而實際上我第一次順著思路寫出來的遞歸是遞歸1蚜厉，這是為什么呢？
思考：
因為遞歸通常是要先去找退出條件的派歌，那么由路徑總和我們知道終止條件就是當左右子樹都為None時弯囊，則不用再往下遞歸了，所以我的遞歸1的終止條件就如同我說的一樣胶果，終止條件設(shè)定好了匾嘱，那么進入下層遞歸的條件也就來了，不能僅以node作為判斷條件早抠，因為以node.left霎烙、node.right進行判斷時就默認了node不能為None，所以必須對左右分支提前進行預先判斷蕊连，確保傳入的節(jié)點不能為None悬垃，所以這種寫法看起來就是同時處理了兩個分支，所以相對于正常的遞歸寫法（遞歸2）的每次處理一個節(jié)點來說邏輯較為繁瑣一點甘苍。
提煉一下：
按照正常邏輯提出的終止條件對于程序來說并不優(yōu)美尝蠕，對于只要關(guān)注當前節(jié)點的正常遞歸來說，變成了需要關(guān)注當前節(jié)點的所有子節(jié)點了载庭，所以并不能被終止條件所迷惑看彼，看透程序執(zhí)行順序的本質(zhì)，嚴格按照遞歸模板走囚聚，僅關(guān)注當前節(jié)點則能使代碼更簡潔靖榕。
參考文獻：
https://labuladong.gitbook.io/algo/shu-ju-jie-gou-xi-lie/er-cha-shu-xi-lie-1
