双向递归

两两交换链表中的节点

• 递归比迭代更加好想，好写，不易出bug

• 但是递归有可能发生爆栈

经典二分查找问题

快速幂

• 和递归的核心思想由大化小完美贴合的两个算法

• 换种递归拆分的方法会让时间复杂度和栈深度降低很多

• 由于每次砍掉一半，递归深度不会太深，没有爆栈风险

---

二叉树的深度优先遍历

• 前序遍历

• 中序遍历

• 后续遍历

斐波那契数列

• 递归树

汉诺塔

• 递归树

• 拆解的时候只考虑当前层

---

二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式。二叉树特点是每个结点最多只能有两棵子树，且有左右之分

遍历（traverse）

• 遍历：访问容器中的每一个数据成员各一次，不重不漏。

  • 不允许某一个或某些元素没有被访问。

  • 不允许某一个或某些元素被访问了一次以上。

• 二叉树的遍历

  • 深度优先遍历

    • 前序遍历(先序遍历)

    • 中序遍历

    • 后序遍历

  • 宽度优先遍历

    • 层序遍历

---

深度优先遍历

• 这是一种“不撞南墙不回头”的策略，主要步骤如下：

  • 沿着当前路径前进

  • 发现一个多叉路口

  • 记住当前路口，以一定行动顺序开始依次向各个方向行动

  • 循环上述三个步骤，直到在当前路径无路可走

  • 返回至最近记录的路口，向下一个方向前进

  • 循环上述所有步骤，直到将所有的地点都走过一次

• 图例：走迷宫

• 分类

  • 前序遍历（Preorder Traversal）
    • 根节点-> 左子树-> 右子树
    • Root -> Left -> Right
  • 后序遍历（Postorder Traversal）
    • 左子树-> 右子树-> 根节点
    • Left -> Right -> Root
  • 中序遍历（Inorder Traversal）
    • 左子树-> 根节点-> 右子树
    • Left -> Root -> Right

---

斐波那契数列

int fibo(int n) {
    if (n <= 2) {
        return n - 1;
    }
    return fibo(n - 1) + fibo(n - 2);
}

优化：记忆化搜索

---

汉诺塔

把 n 个盘子从 'A' 柱移动到 'C' 柱上

递归的定义

• helper(n, start, end, temp, moves)

• 把 n 个盘子从 start 移到 end

• 可以借助 temp 进行移动

• 移动的方案存到 moves 里

递归的拆解

• 把前 n - 1 个盘子从 start 移到 temp

  • helper(n - 1, start, temp, end, moves)

• 把第 n 个盘子从 start 移到 end

• 把前 n - 1 个盘子 temp 移到 end

  • helper(n - 1, temp, end, start, moves)

递归的出口

• n == 1

• 直接把盘子从 start 移到 end

void helper(int n, char start, char end, char temp, List<string moves) {
    if (n == 0) {
	    moves.add(move(start, end));
        return;
    }
    
    helper(n - 1, start, temp, end, moves);
    moves.add(move(start, end));
    helper(n - 1, temp, end, start, moves);
}

public List<string> towerOfHanoi(int n){
    List<string> moves new ArrayList<>();
    helper(n, 'A', 'C', 'B', moves);
    return moves;
}

private String move(char start, char end) {
	return "from " + start + "to " + end;
}

---

巴什博弈

桌子上有一堆石头，你和你的朋友轮流从中拿石头。每一次你们都会从中拿出1到3个石头。拿走最后一个石头的人赢得游戏。游戏开始时，你是先手。

boolean bash(int n) {
    if (n <= 3) {
        return true;
    }
    
    return bash(n - 1) || bash(n - 2) || bash(n - 3);
}

优化：数学规律，n % 4 != 0

二叉树的分治

分治

• 什么是分治

• 和二叉树有什么关系

二叉树的最大深度

最大二叉树

通过遍历序确定二叉树

• 前序遍历和中序遍历树构造二叉树

• 中序遍历和后序遍历树构造二叉树

分治法(Divide and conquer)

将大规模问题拆分为若干个小规模的同类型问题去处理

然后将小规模问题的结果进行合并处理的算法

分治法 VS 递归

• 分治法：分治法是一种算法
• 递归：递归是一种程序设计方式

什么样的数据结构适合分治法？

• 数组：一个大数组可以拆分为若干个不相交的子数组
• 二叉树：整颗二叉树的左子树和右子树都是二叉树

递归的分治法：后序遍历

public 返回结果类型 divideConquer(root) (
    if (root == null) {
	    处理空树应该返回的结果
    }
    
    if (root.left == null && root.right == null) {
        处理叶子应该返回的结果
        如果叶子的返回结果可以通过两个空节点的返回结果得到
        就可以省略这一段代码，一般可省略
    }
    
    左子树的返回结果 = divideConquer(root.left)
    右子树的返回结果 = divideConquer(root.right)
    整棵树的结果 = 按照一定方法合并左右子树的结果

    return 整颗树的结果
}

---

二叉树最大深度

递归的定义

• maxDepth(root)

• 以 root 为根的二叉树的最大深度是多少

递归的拆解

• maxDepth(root.left)

• maxDepth(root.right)

递归的出口

• root 是一棵空树的根

int depth(TreeNode root) {
    if (root == null) {
        return 0;
    }
    return Math.max(depth(root.left), depth(root.right));
}

---

最大二叉树

给定一个没有重复元素的整数数组。根据此数组构建的最大二叉树定义如下：

• root是数组中的最大数字

• 左子树是根据最大数字左侧的子数组构建的最大二叉树。

• 右子树是根据最大数字右侧的子数组构建的最大二叉树。

递归的定义

• buildTree(nums, start, end)

• 以 nums数组的 start ~ end 区间构建最大二叉树

递归的拆解

• 找到 nums 数组 start ~ end 区间上的最大元素位置记做 position

• root = nums[position]

• root.left = buildTree(nums, start, position - 1);

• root.right = buildTree(nums, position + 1, end);

递归的出口

• nums 数组或 start ~ end 区间为空的时候

TreeNode build(int[] nums, int i, int j) {
    if (i > j) return null;
    
    int maxIdx = i;
    for (int k = i; k <= j; k++) {
        if (nums[k] > nums[maxIdx]) {
            maxIdx = k;
        }
    }
    TreeNode root = new TreeNode(nums[maxIdx]);
    root.left = build(nums, i, maxIdx - 1);
    root.right = build(nums, maxIdx + 1, j);
    return root
}