二叉树思维模型

荒流2024年6月6日大约 4 分钟约 1229 字

参考：东哥带你刷二叉树（纲领篇） | labuladong 的算法笔记。

两种思维模式

二叉树解题的思维模式分两类：

是否可以通过遍历一遍二叉树得到答案？
- 如果可以，通常用一个 void traverse(...) 函数配合外部变量来实现，这叫遍历的思维模式。
- 这类思路对应着回溯算法核心框架，在写回溯问题时，函数签名通常写作 void backtrack(...)。
是否可以定义一个递归函数，通过子问题（子树）的答案推导出原问题的答案？
- 如果可以，写出这个递归函数的定义，并充分利用这个函数的返回值，返回值一般是子问题的计算结果，这叫分解问题的思维模式。
- 这类思路对应着动态规划核心框架，在写动态规划问题时，函数签名通常写作 ReturnType dp(...)

无论使用哪种思维模式，你都需要思考：

如果单独抽出一个二叉树节点，它需要做什么事情？
其他的节点不用你操心，递归函数会帮你在所有节点上执行相同的操作。
需要在什么时候（前/中/后序位置）做？

遍历框架

二叉树遍历框架：

void traverse(TreeNode root) {
    if (root == null) {
        return;
    }
    // 这里属于前序位置
    traverse(root.left);
    // 这里属于中序位置
    traverse(root.right);
    // 这里属于后序位置
}

先不管所谓前中后序，单看 traverse 函数，你说它在做什么事情？

其实它就是一个能够遍历二叉树所有节点的一个函数，和你遍历数组或者链表本质上没有区别：

/* 迭代遍历数组 */
void traverse(int[] arr) {
    for (int i = 0; i < arr.length; i++) {

    }
}

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

/* 迭代遍历单链表 */
void traverse(ListNode head) {
    for (ListNode p = head; p != null; p = p.next) {

    }
}

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

单链表和数组的遍历可以是迭代的，也可以是递归的。二叉树这种结构无非就是二叉链表，由于没办法简单改写成迭代形式，所以一般说二叉树的遍历框架都是指递归的形式。

前中后序是遍历二叉树过程中处理每一个节点的三个特殊时间点，绝不仅仅是三个顺序不同的 List：

前序位置的代码在刚刚进入一个二叉树节点的时候执行；
后序位置的代码在将要离开一个二叉树节点的时候执行；
中序位置的代码在一个二叉树节点左子树都遍历完，即将开始遍历右子树的时候执行。

你注意本文的用词，我一直说前中后序「位置」，就是要和大家常说的前中后序「遍历」有所区别：你可以在前序位置写代码往一个 List 里面塞元素，那最后得到的就是前序遍历结果；但并不是说你就不可以写更复杂的代码做更复杂的事。

你可以发现每个节点都有「唯一」属于自己的前中后序位置，所以说前中后序遍历是遍历二叉树过程中处理每一个节点的三个特殊时间点。

这里你也可以理解为什么多叉树没有中序位置，因为二叉树的每个节点只会进行唯一一次左子树切换右子树，而多叉树节点可能有很多子节点，会多次切换子树去遍历，所以多叉树节点没有「唯一」的中序遍历位置。

说了这么多基础的，就是要帮你对二叉树建立正确的认识，然后你会发现：二叉树的所有问题，就是让你在前中后序位置注入巧妙的代码逻辑，去达到自己的目的，你只需要单独思考每一个节点应该做什么，其他的不用你管，抛给二叉树遍历框架，递归会在所有节点上做相同的操作。

以树的角度看回溯/动态规划/DFS

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

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

二叉树思维模型

两种思维模式

遍历框架

以树的角度看回溯/动态规划/DFS

详情