二叉树

数据结构：数据域+左子节点指针+右子节点指针

遍历：前序遍历，中序遍历，后续遍历（使用递归，结束条件为根节点为空，只是递归的顺序不同）

层次遍历：分层遍历二叉树（按层次从上到下，从左到右）迭代，相当于广度优先搜索，使用队列实现。队列初始化，将根节点压入队列。当队列不为空，进行如下操作：弹出一个节点，访问，若左子节点或右子节点不为空，将其压入队列。

常见算法（主要算法都是递归）：

（1）求二叉树的节点个数（递归）

如果二叉树不为空，二叉树节点个数 = 左子树节点个数 + 右子树节点个数 + 1

（2）求二叉树的深度（高度）（递归）

如果二叉树不为空，二叉树的深度 = max(左子树深度， 右子树深度) + 1

3. 求二叉树第k层的节点个数（递归）

求以root为根的k层节点数目，等价于求以root左孩子为根的k-1层（因为少了root）节点数目 加上以root右孩子为根的k-1层（因为 少了root）节点数目。

4.求二叉树中叶子节点的个数（递归）

如果二叉树为空，返回0

如果二叉树是叶子节点，返回1

如果二叉树不是叶子节点，二叉树的叶子节点数 = 左子树叶子节点数 + 右子树叶子节点数

队列

1.用两个栈实现一个队列，并分别实现在队列尾部插入结点和在头部删除结点的功能。

将几个元素压入其中一个栈的时候，的确是"先进后出"，但是可以将这些元素再压入另一个栈，这样就可以将最后一个元素，也就是先压入的元素放在栈顶，也就是"先进先出"了。

Stack<string > stack = new Stack<string>();

入栈：stack.push()。 出栈：stack.pop()，经常使用辅助栈

栈：

1.

2.