1、为何要从树下手

回溯、分治、动态规划，在刷了这么多题之后的体会就是其实都是树的遍历，大多数算法与树都脱不了干系，在东哥的指引下，开始树的模板总结：

2、树的遍历的框架特点

# 所谓的树的遍历的几行破代码
def find_next(root):
    if xxx:
        return
    # 前序遍历
        do_some()
    find_next(root.left)
    # 中序遍历
        do_some()
    find_next(root.right)
    # 后序遍历
        do_some()

3、树框架的经典案例

东哥举了两个典型的例子，虽然直观上没有联系，但都暗藏玄机，如下

3.1快速排序

简单概要一下快排的精髓，从当前需要排序的数组nums中取一个截断点(取数组第一个也好，随机取也好)，这个截断点的作用就是分割数组，小于该点的放前面，大于该点的放后面，便产生左右两个子数组，之后对左右数组递归执行上述逻辑，当数组的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)

妥妥的前序遍历的节奏，先找根，再依次处理左右节点，伪代码不过瘾，上干货

    #  图方便用了费内存的写法，可以试试在原数组上修改
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归并排序

同样简单概括一下归并排序的精髓，其实也就是所谓的分治思想，把原有数组一分为二，分别排序，最后再合并，递归则体现在分别排序里，分治的思想体现在，把问题设计成重复子问题，我要排一个大的，只要排两个小的，最终通过后续遍历的回溯特性依次把小的数组，组装起来复原成初始要求的大数组。

提炼一下：

以我的理解串一下就是后续遍历这种递归模式，易构成回溯的特性，从而能实现利用分治思想设计的解决方案，往后提前拓展一下可以体会到，递归可以实现逆向分治(自上而下的拆解)，而动态规划则是分治的正向体现(自下而上的组装)。

#  归并排序伪代码
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、写法对比

随便举一个刷题的例子，每次写递归总觉的自己写的不优美，这是为啥呢？
个人觉得这和我们平常的思维方式有关，比如这题路径总和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
            # 处理当前节点
            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)
            # 清理当前节点
            path.pop()
        dfs(root)
        return ans

递归2的方法是不是比第一种要好很多呢，代码看着思路也清晰，而实际上我第一次顺着思路写出来的递归是递归1，这是为什么呢？

思考：

因为递归通常是要先去找退出条件的，那么由路径总和我们知道终止条件就是当左右子树都为None时，则不用再往下递归了，所以我的递归1的终止条件就如同我说的一样，终止条件设定好了，那么进入下层递归的条件也就来了，不能仅以node作为判断条件，因为以node.left、node.right进行判断时就默认了node不能为None，所以必须对左右分支提前进行预先判断，确保传入的节点不能为None，所以这种写法看起来就是同时处理了两个分支，所以相对于正常的递归写法（递归2）的每次处理一个节点来说逻辑较为繁琐一点。

提炼一下：

按照正常逻辑提出的终止条件对于程序来说并不优美，对于只要关注当前节点的正常递归来说，变成了需要关注当前节点的所有子节点了，所以并不能被终止条件所迷惑，看透程序执行顺序的本质，严格按照递归模板走，仅关注当前节点则能使代码更简洁。

参考文献：
https://labuladong.gitbook.io/algo/shu-ju-jie-gou-xi-lie/er-cha-shu-xi-lie-1