1. Recursion与数学计算的结合

LC50 Pow(x, n) a^b

数学计算常见陷阱:(Corner Case)

1) 0 as the denominator
2) 1/3 as an integer? or float? 精度问题
3) 0^0

public double power(double a, double b) {
    if (a == 0 && b <= 0) {
        return -1;
    } else if (b < 0) {
        return 1 / (double)pow(a,b);
    } else {
        return (double) pow(a, b);
    }
}

public int pow(int a, int b) {
    if (b == 0) { return 1;}

    int halfResult = pow(a, b/2);
    if (b % 2 == 0){
        return halfResult * halfResult;
    } else {
        return halfResult * halfResult * a;
}

2. Recursion与1D or 2D Array的结合

1D Array - Merge Sort, Quick Sort

2D Array

LC51 N-Queens

1 逐层(row by row)递归：8 queen -> n queen

xQxxxxxx
xxxQxxxx xxQxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxQx
- Recursive rule: For the i-th queen on the i-th row, we must make sure the Qi does no conflict with all previous queens that have been placed on the board. int Position[N] = {1 2 3 5 ...}
- Base Case: The last row is done, 0 row left
- Recursive rule: iff position(i,j)valid - >go to the next roe:(i+1) Time = O($$8^8$$) -> O(8!)
2 How to print 2D array in spiral order (NxN) x x x x x x x x x x x x x x x x x x x x

Recursive rule: size = size - 2 offset = offset + 1
旋转矩阵！

3. Recursion和LinkedList的结合

Q1 Reverse a linked list

Q2 Reverse linked list pair by pair

4. Recursion和String的结合

Q1 Reverse a String using recursion

abcd -> dcba
Q2 A word such as "book" can be abbreviated to 4, "1o1k", "b3", "b2k", etc. Given a string and an abbreviation, return if the string matches the abbreviation. Assume the original string only contains alphabetic characters.

5. Recursion和Tree的结合

Binary tree 往往是最常见的，和recursion结合最紧密的面试题目类型

树本身就是Recursive的结构！
每层的node具备的性质，传递的值和下一层的性质往往一致。比较容易定义recursive rule
Base case(generally):null pointer under the leaf node

Tree + Recursion 第一类问题:从下往上反值(int ,bool,etc.)

* 从下往上反值 - getHeight(Node root)
* 从下往上反值 - 统计tree里每个node的左子树有多少个node？
* 从下往上返值 - Find the node with **max difference** in the total number of descendents in its left subtree and right subtree

【Way of thinking】 (相当于后序遍历)

1.What do you expect from your lchild/rhild? (usually it is the return type of the recursion type)
2.What do you want to do in the current layer?
3.What do you want to report to your parent?(same as Q1 == Q3)

LC236 Lowest Common Ancestor of a Binary Tree

从下往上返值，最最经典例题! LCA

Method1

use two additional arrays to buffer the prefix from root to a and from root to b

Method2 (Recursion)

Case1: if a is NOT the ancestor of b (a和b直接隶属)

  * 1.1 left == null, right == null, return null
  * 1.2 left and right reutrn c
  * 1.3 either left or right return NOT null, return not NULL

Case2: if a is the ancestor of b (a和b不直接隶属)

  * same thing

Follow Up

What if either a or b is not int the tree. Can this method take care of this case? A - It depends on your assumption.
Assuming that both a and b are in the tree:
- case1: result = c (c != a && c != b) it means a and b不直接隶属
- case2a: result = a (a has a descendent which is b)
- case2b: result = b (b has a descendent which is a)

Recursion应用