Gauss Zhou

Appearance

基础 二叉树 ​

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

  • 1、是否可以通过遍历一遍二叉树得到答案？如果可以，用一个 traverse 函数配合外部变量来实现，这叫 “遍历” 的思维模式。
  • 2、是否可以定义一个递归函数，通过子问题 (子树) 的答案推导出原问题的答案？如果可以，写出这个递归函数的定义，并充分利用这个函数的返回值，这叫 “分解问题” 的思维模式。

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

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

遍历框架 ​

cpp
/* 基本的二叉树节点 */
class TreeNode {
    int val;
    TreeNode left, right;
}

void traverse(TreeNode root) {
    traverse(root.left);
    traverse(root.right);
}
cpp
/* 基本的 N 叉树节点 */
class TreeNode {
    int val;
    TreeNode[] children;
}

void traverse(TreeNode root) {
    for (TreeNode child : root.children)
        traverse(child);
}

二叉树的重要性 ​

快速排序就是个二叉树的前序遍历，归并排序就是个二叉树的后序遍历。

快速排序的代码框架如下：

先构造分界点，然后去左右子数组构造分界点，你看这不就是一个二叉树的前序遍历吗

js
function sort(nums, lo, hi) {
    // 通过交换元素构建分界点 p
    let p = partition(nums, lo, hi);
    sort(nums, lo, p - 1);
    sort(nums, p + 1, hi);
}

归并排序的代码框架如下：

js
function sort(nums, lo, hi) {
    let mid = (lo + hi) / 2;
    // 排序 nums[lo..mid]
    sort(nums, lo, mid);
    // 排序 nums[mid+1..hi]
    sort(nums, mid + 1, hi);
    merge(nums, lo, mid, hi);
}

深入理解前中后序 ​

cpp
/* 迭代遍历数组 */
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);
    // 后序位置
}
cpp
/* 迭代遍历单链表 */
void traverse(ListNode head) {
    for (ListNode p = head; p != null; p = p.next) {

    }
}

/* 递归遍历单链表 */
void traverse(ListNode head) {
    if (head == null) {
        return;
    }
    // 前序位置
    traverse(head.next);
    // 后序位置
}
js
/* 递归遍历单链表，倒序打印链表元素 */
function traverse(head) {
    if (head == null) {
        return;
    }
    traverse(head.next);
    // 后序位置
    print(head.val);
}

两种解题思路 ​

二叉树题目的递归解法可以分两类思路，第一类是遍历一遍二叉树得出答案，第二类是通过分解问题计算出答案，这两类思路分别对应着回溯算法核心框架和动态规划核心框架