Recursion Note

Recursion 需要掌握的知识点： 1）表象上：function calls itself 2）实质上：Boil down a big problem to smaller ones (size n depends on size n - 1, or n - 2 or ... n/2) 3) Implementation 上： a) Base cases: smallest problem to solve b) Recursive rule: how to make the problem smaller (if we can resolve the same problem but with a smaller size, then what is left to do for the current problem size n)

Trick:所以前面的node的个数的总和，都没有最后一层node的个数多，因此我们分析tree的time complexity，往往只看最后一层node的个数。