二叉树系列算法核心纲领

func sort(nums []int, lo int, hi int) {
    if lo >= hi {
        return
    }
    // ****** 前序位置 ******
    // 对 nums[lo..hi] 进行切分，将 nums[p] 排好序
    // 使得 nums[lo..p-1] <= nums[p] < nums[p+1..hi]
    p := partition(nums, lo, hi)

    // 去左右子数组进行切分
    sort(nums, lo, p-1)
    sort(nums, p+1, hi)
}

// 定义：排序 nums[lo..hi]
func sort(nums []int, lo, hi int) {
    if lo == hi {
        return
    }
    mid := (lo + hi) / 2
    // 利用定义，排序 nums[lo..mid]
    sort(nums, lo, mid)
    // 利用定义，排序 nums[mid+1..hi]
    sort(nums, mid+1, hi)

    // ****** 后序位置 ******
    // 此时两部分子数组已经被排好序
    // 合并两个有序数组，使 nums[lo..hi] 有序
    merge(nums, lo, mid, hi)
}

// 二叉树的遍历框架
func traverse(root *TreeNode) {
    if root == nil {
        return
    }
    // 前序位置
    traverse(root.Left)
    // 中序位置
    traverse(root.Right)
    // 后序位置
}

// 迭代遍历数组
func traverse(arr []int) {
    for i := 0; i < len(arr); i++ {

    }
}

// 递归遍历数组
func traverse(arr []int, i int) {
    if i == len(arr) {
        return;
    }
    // 前序位置
    traverse(arr, i + 1)
    // 后序位置
}


// 迭代遍历单链表
func traverse(head *ListNode) {
    for p := head; p != nil; p = p.Next {

    }
}

// 递归遍历单链表
func traverse(head *ListNode) {
    if head == nil {
        return;
    }
    // 前序位置
    traverse(head.Next)
    // 后序位置
}

// 递归遍历单链表，倒序打印链表元素
func traverse(head *ListNode) {
    if head == nil {
        return
    }
    traverse(head.Next)
    // 后序位置
    fmt.Println(head.Val)
}

Tip
这里说一下我的函数命名习惯：二叉树中用遍历思路解题时函数签名一般是 void traverse(...)，没有返回值，靠更新外部变量来计算结果，而用分解问题思路解题时函数名根据该函数具体功能而定，而且一般会有返回值，返回值是子问题的计算结果。

与此对应的，你会发现我在
回溯算法核心框架 中给出的函数签名一般也是没有返回值的 void backtrack(...)，而在
动态规划核心框架 中给出的函数签名是带有返回值的 dp 函数。这也说明它俩和二叉树之间千丝万缕的联系。

虽然函数命名没有什么硬性的要求，但我还是建议你也遵循我的这种风格，这样更能突出函数的作用和解题的思维模式，便于你自己理解和运用。

func maxDepth(root *TreeNode) int {
    // 记录遍历到的节点的深度
    depth := 0
    // 记录最大深度
    res := 0

    traverse(root, &depth, &res)
    return res
}

// 遍历二叉树
func traverse(root *TreeNode, depth *int, res *int) {
    if root == nil {
        return
    }

    // 前序遍历位置（进入节点）增加深度
    *depth++
    // 遍历到叶子节点时记录最大深度
    if root.Left == nil && root.Right == nil {
        *res = max(*res, *depth)
    }
    traverse(root.Left, depth, res)
    traverse(root.Right, depth, res)

    // 后序遍历位置（离开节点）减少深度
    *depth--
}

// 遍历的思路
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

// 分解问题的思路
func maxDepth(root *TreeNode) int {
    // 定义：输入一个节点，返回以该节点为根的二叉树的最大深度
    if root == nil {
        return 0
    }
    // 利用定义，计算左右子树的最大深度
    leftMax := maxDepth(root.Left)
    rightMax := maxDepth(root.Right)

    // 根据左右子树的最大深度推出原二叉树的最大深度
    // 整棵树的最大深度等于左右子树的最大深度取最大值，
    // 然后再加上根节点自己
    return 1 + max(leftMax, rightMax)
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

// 用遍历的思路计算前序遍历结果
func preorderTraversal(root *TreeNode) []int {

    // 存放前序遍历结果
    var res []int

    var traverse func(root *TreeNode)
    traverse = func(root *TreeNode) {
        if root == nil {
            return
        }
        // 前序位置
        res = append(res, root.Val)
        traverse(root.Left)
        traverse(root.Right)
    }

    traverse(root)
    return res
}

// 定义：输入一棵二叉树的根节点，返回这棵树的前序遍历结果
func preorderTraversal(root *TreeNode) []int {
	var res []int
	if root == nil {
		return res
	}
	// 前序遍历的结果，root.Val 在第一个
	res = append(res, root.Val)
	// 利用函数定义，后面接着左子树的前序遍历结果
	res = append(res, preorderTraversal(root.Left)...)
	// 利用函数定义，最后接着右子树的前序遍历结果
	res = append(res, preorderTraversal(root.Right)...)
	return res
}

仔细观察，前中后序位置的代码，能力依次增强。

前序位置的代码只能从函数参数中获取父节点传递来的数据。

中序位置的代码不仅可以获取参数数据，还可以获取到左子树通过函数返回值传递回来的数据。

后序位置的代码最强，不仅可以获取参数数据，还可以同时获取到左右子树通过函数返回值传递回来的数据。

所以，某些情况下把代码移到后序位置效率最高；有些事情，只有后序位置的代码能做。

// 二叉树遍历函数
void traverse(TreeNode root, int level) {
    if (root == null) {
        return;
    }
    // 前序位置
    printf("节点 %s 在第 %d 层", root.val, level);
    traverse(root.left, level + 1);
    traverse(root.right, level + 1);
}

// 这样调用
traverse(root, 1);

// 定义：输入一棵二叉树，返回这棵二叉树的节点总数
int count(TreeNode root) {
    if (root == null) {
        return 0;
    }
    int leftCount = count(root.left);
    int rightCount = count(root.right);
    // 后序位置
    printf("节点 %s 的左子树有 %d 个节点，右子树有 %d 个节点",
            root, leftCount, rightCount);

    return leftCount + rightCount + 1;
}

这两个问题的根本区别在于

一个节点在第几层，你从根节点遍历过来的过程就能顺带记录，用递归函数的参数就能传递下去；而以一个节点为根的整棵子树有多少个节点，你必须遍历完子树之后才能数清楚，然后通过递归函数的返回值拿到答案。

结合这两个简单的问题，你品味一下后序位置的特点，只有后序位置才能通过返回值获取子树的信息。

那么换句话说，一旦你发现题目和子树有关，那大概率要给函数设置合理的定义和返回值，在后序位置写代码了。

// 记录最大直径的长度
func diameterOfBinaryTree(root *TreeNode) int {
    maxDiameter := 0

    // 遍历二叉树
    var traverse func(root *TreeNode)
    traverse = func(root *TreeNode) {
        if root == nil {
            return
        }
        // 对每个节点计算直径
        leftMax := maxDepth(root.Left)
        rightMax := maxDepth(root.Right)
        myDiameter := leftMax + rightMax
        // 更新全局最大直径
        maxDiameter = max(maxDiameter, myDiameter)

        traverse(root.Left)
        traverse(root.Right)
    }
    traverse(root)
    return maxDiameter
}

// 计算二叉树的最大深度
func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    leftMax := maxDepth(root.Left)
    rightMax := maxDepth(root.Right)
    return 1 + max(leftMax, rightMax)
}

// 辅助函数，求两个数的最大值
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func diameterOfBinaryTree(root *TreeNode) int {
    // 记录最大直径的长度
    maxDiameter := 0

    var maxDepth func(root *TreeNode) int
    maxDepth = func(root *TreeNode) int {
        if root == nil {
            return 0
        }
        leftMax := maxDepth(root.Left)
        rightMax := maxDepth(root.Right)
        // 后序位置，顺便计算最大直径
        myDiameter := leftMax + rightMax
        maxDiameter = max(maxDiameter, myDiameter)
        return 1 + max(leftMax, rightMax)
    }

    maxDepth(root)

    return maxDiameter
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

思考题：请你思考一下，运用后序位置的题目使用的是「遍历」的思路还是「分解问题」的思路？

利用后序位置的题目，一般都使用「分解问题」的思路。因为当前节点接收并利用了子树返回的信息，这就意味着你把原问题分解成了当前节点 + 左右子树的子问题。

划重点
动归/DFS/回溯算法都可以看做二叉树问题的扩展，只是它们的关注点不同：

动态规划算法属于分解问题（分治）的思路，它的关注点在整棵「子树」。
回溯算法属于遍历的思路，它的关注点在节点间的「树枝」。
DFS 算法属于遍历的思路，它的关注点在单个「节点」。

// 定义：输入一棵二叉树，返回这棵二叉树的节点总数
func count(root *TreeNode) int {
    if root == nil {
       return 0
    }
    // 当前节点关心的是两个子树的节点总数分别是多少
    // 因为用子问题的结果可以推导出原问题的结果
    leftCount := count(root.Left)
    rightCount := count(root.Right)
    // 后序位置，左右子树节点数加上自己就是整棵树的节点数
    return leftCount + rightCount + 1
}

// f(n) 计算第 n 个斐波那契数
func fib(n int) int {
    // base case
    if n == 0 || n == 1 {
        return n
    }
    return fib(n-1) + fib(n-2)
}

void traverse(TreeNode root) {
    if (root == null) return;
    printf("从节点 %s 进入节点 %s", root, root.left);
    traverse(root.left);
    printf("从节点 %s 回到节点 %s", root.left, root);

    printf("从节点 %s 进入节点 %s", root, root.right);
    traverse(root.right);
    printf("从节点 %s 回到节点 %s", root.right, root);
}

// 多叉树节点
class Node {
    int val;
    Node[] children;
}

void traverse(Node root) {
    if (root == null) return;
    for (Node child : root.children) {
        printf("从节点 %s 进入节点 %s", root, child);
        traverse(child);
        printf("从节点 %s 回到节点 %s", child, root);
    }
}

// 回溯算法框架
void backtrack(...) {
    // base case
    if (...) return;

    for (int i = 0; i < ...; i++) {
        // 做选择
        ...

        // 进入下一层决策树
        backtrack(...);

        // 撤销刚才做的选择
        ...
    }
}

// 回溯算法核心部分代码
void backtrack(int[] nums) {
    // 回溯算法框架
    for (int i = 0; i < nums.length; i++) {
        // 做选择
        used[i] = true;
        track.addLast(nums[i]);

        // 进入下一层回溯树
        backtrack(nums);

        // 取消选择
        track.removeLast();
        used[i] = false;
    }
}

func traverse(root *TreeNode) {
    if root == nil {
        return
    }
    // 遍历过的每个节点的值加一
    root.Val++
    traverse(root.Left)
    traverse(root.Right)
}

// DFS 算法核心逻辑
void dfs(int[][] grid, int i, int j) {
    int m = grid.length, n = grid[0].length;
    if (i < 0 || j < 0 || i >= m || j >= n) {
        return;
    }
    if (grid[i][j] == 0) {
        return;
    }
    // 遍历过的每个格子标记为 0
    grid[i][j] = 0;
    dfs(grid, i + 1, j);
    dfs(grid, i, j + 1);
    dfs(grid, i - 1, j);
    dfs(grid, i, j - 1);
}

import "fmt"

// DFS 算法把「做选择」「撤销选择」的逻辑放在 for 循环外面
func Dfs(root *Node) {
    if root == nil {
        return
    }
    // 做选择
    fmt.Printf("enter node %v\n", root)
    for _, child := range root.children {
        Dfs(child)
    }
    // 撤销选择
    fmt.Printf("leave node %v\n", root)
}

// 回溯算法把「做选择」「撤销选择」的逻辑放在 for 循环里面
func Backtrack(root *Node) {
    if root == nil {
        return
    }
    for _, child := range root.children {
        // 做选择
        fmt.Printf("I'm on the branch from %v to %v\n", root, child)
        Backtrack(child)
        // 撤销选择
        fmt.Printf("I'll leave the branch from %v to %v\n", child, root)
    }
}

// 输入一棵二叉树的根节点，层序遍历这棵二叉树
func levelTraverse(root *TreeNode) {
    if root == nil {
        return
    }

    q := make([]*TreeNode, 0)
    q = append(q, root)
    depth := 1

    // 从上到下遍历二叉树的每一层
    for len(q) > 0 {
        sz := len(q)

        // 从左到右遍历每一层的每个节点
        for i := 0; i < sz; i++ {
            cur := q[0]
            q = q[1:]

            // 将下一层节点放入队列
            if cur.Left != nil {
                q = append(q, cur.Left)
            }
            if cur.Right != nil {
                q = append(q, cur.Right)
            }
        }
        depth++
    }
}