递归的实现、特性以及思维要点

树的面试题一般都是 递归

    1. 节点的定义
    1. 重复性（自相似性）

递归 Recursion

  • 递归 - 循环

  • 通过函数体来进行的循环

  • 计算 n! ```python

    n! = 1 2 3 … n

def Factorial(n): if n <= 1: return 1 return n * Factorial(n - 1)

  3. <a name="7aFkK"></a>
  4. ## 递归的步骤
  6. - 1. 递归终结条件
  7. - 2. 处理当前层逻辑
  8. - 3. 下探到下一层
  9. - 4. 清理当前层
  11. <a name="vO5zi"></a>
  12. ## Python 代码模板
  14. ```python
  15. def recursion(level, param1, param2, ...):
  16.     # recursion terminator
  17.     if level > MAX_LEVEL:
  18.         process_result
  19.         return
  21.     # process logic in current level
  22.     process(level, data...)
  24.     # drill down
  25.     self.recursion(level + 1, p1, ...)
  27.     # reverse the current level status if needed

Java 代码模板

public void recur(int level, int param) {
    // terminator
    if (level > MAX_LEVEL) {
        // process result
        return;
    }

    // process current logic
    process(level, param);

    // drill down
    recur(level: level + 1, newParam);

    // restore current status
}

递归的思维要点

    1. 不要人肉进行递归、也就是画图（最大误区）
    1. 找到最近最简方法，将其拆解成可重复解决的问题（重复子问题）
    1. 数学归纳法

实战题目：爬楼梯、括号生成等问题

  • 爬楼梯（70）

    • 1：1
    • 2：2
    • 3：f(1) + f(2)
      • // 跨一步台阶，从2这个台阶走上来；跨两步，从1这个台阶走上来
      • 1 的台阶的总走法，跨两步跨上3；或是 2 这个台阶的总走法，跨一步跨上 3
    • 4：f(2) + f(3)
    • …
    • f(n) = f(n -1) + f(n - 2): Fibonacci

  • 括号生成（22）

  • 翻转二叉树（226）
  • 验证二叉搜索树（98）
  • 二叉树的最大深度（104）
  • 二叉树的最小深度（111）
  • 二叉树的最近公共祖先（236）