- 面对问题，理解了思路，但是没有任何想法的时候，不妨从n=1 n=2开始分析下，然后找到递推公式进而成功accept!
【二叉树的构建】
- 已知前序和中序遍历序列可以确定这个二叉树。
- 已知中序和后序遍历序列可以确定这个二叉树。
- 层次遍历和后序遍历也可以确定二叉树。
- 二叉排序树和其他遍历序列的结合可以确定二叉树。
构建的思路是：因为树的定义，本身就是一个递归的定义，那么由遍历序列构建树的时候，解决问题的思路往往就是由已知条件，找出树的根节点，然后把大问题，划分成小的问题，现在小的问题是，左右两个子树的问题，返现左右两个子树和原问题是一模一样的，所以可以用递归来解决问，联系子问题和大问题的纽带是当前这颗树的根节点。递归结束条件是子问题里面只剩下一个节点的情况。
【二叉树的遍历】
二叉树的问题好多本质上是二叉树的遍历问题。深入理解递归遍历和迭代遍历的流程是解决问题的关键。
二叉树的前序、中序、后序遍历都可以看成是DFS，即深度优先遍历，共有3！=6种DFS方法，其他的三种是root->r->l， r->root->l，r->l->root。注意不要小看这三种不常见的DFS。威力无穷而且代码短小。尤其是root->r->l这种深度遍历经常用到，后面的两种r->root->l，r->l->root不经常用到，管理是理解这中遍历本质上都是DFS。二叉树的镜像问题，以及两个二叉树的对比问题，用这种DFS代码短小简洁。root->r->l先遍历根节点，然后在遍历这个根节点的右子树的根节点，然后递归对右子树做遍历，
遍历完事儿之后再递归遍历左子树。注意这种遍历方法很常用。
前序，中序，后序遍历的非递归实现都是用栈实现的，root->r->l的非递归实现也是用栈实现的。其实只不过说递归用的是系统栈而已。
二叉树的层次遍历是用队列实现的。
【二叉树的递归】
二叉树本身就是一个递归的数据结构，因此往往关于二叉树的问题都能用递归的方法来解决，其实也可以借助队列或者栈用迭代来解决。递归一定是深度搜索，二叉树的遍历除了层次遍历以外其他的都是深度搜索，
【二叉查找树】
二叉查找树，第一个要想到的是中序遍历，因为中序遍历的结果是有序的。提到二叉查找树，就得想到二叉查找树的递归定义，左子树的节点值都小于根节点，右子树的节点值都大于根节点。
二叉查找树的规律，有二叉查找树，延伸出AVL树，和红黑树，后两者都是自平衡的二叉查找树。根据二叉查找树的定义，找规律的问题，实质上是一个递推的问题(当然可以递推来求解，也可以迭代来求解)，二叉查找树（Binary Search Tree），也称有序二叉树（ordered binary tree）,排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树：若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；任意节点的左、右子树也分别为二叉查找树。没有键值相等的节点（no duplicate nodes）。二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低。为O(log n)。二叉查找树是基础性数据结构，用于构建更为抽象的数据结构，如集合、multiset、关联数组等。AVL 是自平衡的二叉查找树在计算机科学中，AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为一，所以它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下都是O（log n）。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。红黑树(可以当一个堆用)mutiset 就是红黑树实现的，mutiset允许值重复，红黑树是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。但它的操作有着良好的最坏情况运行时间，并且在实践中是高效的: 它可以在O(log n)时间内做查找，插入和删除，这里的n是树中元素的数目。虽然mutiset使用红黑树(一种自平衡的二叉查找树)实现的，是可以当作一个堆来使用的效率很高，一下代码模拟了入堆和出堆的过程。大顶堆：
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <set>
using namespace std;
int main()
{
//初始化数据到红黑树中，
int num[] = {3, 5, 2, 1, 6, 4, 8, 7};
multiset<int, greater<int> > intMultiSet;
for (int i = 0; i < 8; ++i)
{
intMultiSet.insert(num[i]);
}
while(!intMultiSet.empty())
{
multiset<int, greater<int> >::iterator iterGreatest = intMultiSet.begin();
cout << *iterGreatest << " ";
intMultiSet.erase(iterGreatest);
}
cout << endl;
return 0;
}输出：8 7 6 5 4 3 2 1小顶堆:
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <set>
using namespace std;
int main()
{
//初始化数据到红黑树中，
int num[] = {3, 5, 2, 1, 6, 4, 8, 7};
multiset<int, less<int> > intMultiSet;
for (int i = 0; i < 8; ++i)
{
intMultiSet.insert(num[i]);
}
while(!intMultiSet.empty())
{
multiset<int, less<int> >::iterator iterSmallest = intMultiSet.begin();
cout << *iterSmallest << " ";
intMultiSet.erase(iterSmallest);
}
cout << endl;
return 0;
}输出：1 2 3 4 5 6 7 8