递归
必须满足三个条件：
1. 一个问题的解可以分解为几个子问题的解何为子问题
2. 这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样
3. 存在递归终止条件
编写思想：
1.关注父问题和子问题之间的关系： 构建递归表达式
2.寻找递归的终止条件
例子：
1.假如这里有 n 个台阶，每次你可以跨 1 个台阶或者 2 个台阶，请问走这 n 个台阶有多少种走法？
递归公式和终止条件：
重点： 明确输入的变量是什么（台阶数），输出的是什么的数量（方法）
2.二叉树 后续遍历
明确什么时候进行节点值的输出：
前序： 出左右
中序： 左出右
后序： 左右出
缺点： 递归重复不断调用函数，进行压栈出栈，效率很低
1.对应上面台阶的例子
2.遍历二叉树（迭代）
前序遍历迭代算法（144）
在迭代算法中，思路演变成，每到一个节点 A，就应该立即访问它。因为，每棵子树都先访问其根节点。对节点的左右子树来说，也一定是先访问根。在 A 的两棵子树中，遍历完左子树后，再遍历右子树。因此，在访问完根节点后，遍历左子树前，要将右子树压入栈。
后序遍历迭代算法（145）
第一种方法：
后序遍历与前序遍历相对称。
思路： 每到一个节点 A，就应该立即访问它。 然后将左子树压入栈，再次遍历右子树。
遍历完整棵树后，结果序列逆序即可。
第二种方法：
思路：每到一个节点 A，因为根要最后访问，将其入栈。然后遍历左子树，遍历右子树，最后返回到 A。但是出现一个问题，无法区分是从左子树返回，还是从右子树返回。
因此，给 A 节点附加一个标记T。在访问其右子树前，T 置为 True。之后子树返回时，当 T 为 True表示从右子树返回，否则从左子树返回。当 T 为 false 时，表示 A 的左子树遍历完，还要访问右子树。同时，当 T 为 True 时，表示 A 的两棵子树都遍历过了，要访问 A 了。并且在 A 访问完后，A 这棵子树都访问完成了。
中序遍历迭代算法（94）
思路：每到一个节点 A，因为根的访问在中间，将 A 入栈。然后遍历左子树，接着访问 A，最后遍历右子树。
在访问完 A 后，A 就可以出栈了。因为 A 和其左子树都已经访问完成。
