泛型递归、树的递归

树的面试题解法一般都是递归

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

递归 Recursion：

• 又译为递回，在数学与计算机科学中，是指在函数的定义中使用函数自身的方法。
• 递归一词还较为常用于描述以自相似方法重复事物的过程。
• 在数学和计算机科学中，递归指由一种（或多种）简单的基本情况定义的一类对象或方法，并规定其他所有情况都能被还原为其基本情况。
• 斐波那契数列是典型的递归案例
  • F0 = 0（初始值）
  • F1 = 1（初始值）
  • 对所有大于 1 的整数 n：Fn = Fn-1 + Fn-2
• 递归 - 循环
• 通过函数体来进行的循环

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. 不要人肉递归（最大误区）
2. 找到最近最简方法，将其拆解成可重复解决的问题（重复子问题）
3. 数学归纳法思维