递归

必须满足三个条件：

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 和其左子树都已经访问完成。