二叉树类型的题目：
1. 能够结合队列、栈、链表、字符串等很多数据结构。
2. 需要掌握图的基本遍历方式，比如BFS,DFS。
3. 需要掌握递归函数的使用，并自己设计出递归过程。
先序遍历：中 左 右
中序遍历： 左 中 右
后序遍历：左 右 中
正常遍历方式如上面所示，但是不排序有下面三种不常见的遍历：
中 右 左
右 中 左
右 左 中
案例一：
用递归方式和非递归方式分别实现二叉树的先序、中序和后序的遍历打印。
以先序遍历为例：
public void preOrderRecur(Node head){
if(head==null)//树为空直接返回
return;
System.out.print(head.value+" ");
preOrderRecur(head.left);
preOrderRecur(head.right);
}
下面是利用递归的方式实现的前序 中序 和后序遍历！！！时刻需要注意的是递归的终止条件的设置，一定要判断当前root是否为空，或者加上if判断。同时对于每个递归函数中的result，应该是函数的参数，否则如果写在递归函数中进行定义以及初始化就不对了，因为这样的话每调用过一次递归函数就会对result初始化一次！！！
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class TreeToSequence {
public:
vector<vector<int> > convert(TreeNode* root) {
// write code here
vector<vector<int> > result;
//先实现先序遍历
vector<int> preOrderRecur;
preOrderRecur1(root,preOrderRecur);
result.push_back(preOrderRecur);
vector<int> inOrderRecur;
inOrderRecur1(root,inOrderRecur);
result.push_back(inOrderRecur);
vector<int> posOrderRecur;
posOrderRecur1(root,posOrderRecur);
result.push_back(posOrderRecur);
return result;
}
void preOrderRecur1(TreeNode* root,vector<int>& result){
if(root==NULL)//这里一定更要判断一下，否则有可能为空
return;
result.push_back(root->val);
preOrderRecur1(root->left,result);//如果前面不判断root，这里可以提供一个if，也就是if(root->left!=NULL),下面的类似
preOrderRecur1(root->right,result);
}
void inOrderRecur1(TreeNode* root,vector<int>& result){
if(root==NULL)
return;
inOrderRecur1(root->left,result);
result.push_back(root->val);
inOrderRecur1(root->right,result);
}
void posOrderRecur1(TreeNode* root,vector<int>& result){
if(root==NULL)
return;
posOrderRecur1(root->left,result);
posOrderRecur1(root->right,result);
result.push_back(root->val);
}
};
中序遍历和后序遍历的递归方式和上面的实现大体相同。
下面主要介绍以非递归方式实现遍历：
非递归方式实现先序遍历：
具体过程：
1. 首先申请一个新的栈，记为stack；
2. 然后将头节点head压入stack中；
3. 每次从stack中弹出栈顶节点，记为cur，然后打印cur节点的值。如果cur右孩子不为空的话，将cur的右孩子先压入stack中。最后如果cur的左孩子不为空的话，将cur的左孩子压入stack中。
记住：从栈中弹出的时候才能打印它的值。然后将其右左节点入栈！！！
4. 不断重复步骤3，知道stack为空，全部过程结束。
非递归方法实现中序遍历：
具体过程：
1.申请一个新的栈，记为stack，申请一个变量cur，初始时令cur等于头节点。
2. 先把cur节点压入栈中，对以cur节点为头的整颗子树来说，依次把整棵树的左边界压入栈中，即不断令cur=cur.left，然后重复步骤2.
3. 不断重复步骤2，知道发现cur为空，此时从stack中弹出一个节点，记为node。打印node的值，并让cur=node,right,然后继续重复步骤2.
4. 当stack为空并且cur为空时，结束。
注意：只有从stack中弹出之后才能打印，然后才能对其右子树进行遍历。
非递归方式实现后序遍历：
方法一：使用两个栈实现
具体过程如下：
1. 申请一个栈，记为s1，然后将头节点压入s1中。
2. 从s1中弹出的节点记为cur，然后先把cur的左孩子压入s1中，然后把cur1的右孩子压入s1中。
3. 在整个过程中，每一个从s1中弹出的节点都放进第二个栈s2中。
4. 不断重复步骤2和步骤3，直到s1为空，过程停止。
5. 从s2中依次弹出节点并打印，打印的顺序就是后序遍历的顺序了。
方法二：使用给一个栈实现
具体过程如下：
1. 申请一个栈，记为stack，将头节点压入stack，同时设置两个变量h和c。在整个流程中，h代表最近一次弹出并打印的节点，c代表当前stack的栈顶节点，初始时（也就是要将头节点入栈）令h为头节点，c为null。需要注意的是此时的h只是入栈，并没有出栈，并且也没有打印，只有在接下来的过程中h才会代表最近一次弹出并打印的节点。
2. 每次令c等于当前stack的栈顶节点，但是不从stack中弹出节点。此时分一下三种情况：
（1）如果c的左孩子不为空，并且h不等于c的左孩子，也不等于c的右孩子，则把c的左孩子压入stack中。
解释一下也就是说无论h等于c的左孩子还是c的右孩子，都说明c的左子树已经打印完毕了。此时不应该再将c的左孩子放入到stack中。否则说明c的左子树还没有处理过，将其左孩子压入到stack中
（2）如果情况1不成立，并且c的右孩子不为空，并且h不等于c的右孩子，则把c的右孩子压入stack中。
含义是如果h为c的右孩子，说明c的右子树已经打印完毕了，此时不应该将c的右孩子放入到stack中。否则说明右子树还没有处理过，此时将c的右孩子放入到stack中。
（3）如果情况1和情况2都不成立，那么从stack中弹出c并打印，然后令h等于c。
此时，说明c的左子树和c的右子树都已经打印完毕了。
（3）如果情况1和情况2都不成立，那么从stack中弹出c并打印，然后令h等于c。
3. 一直重复步骤2，直到stack为空，过程停止。
需要注意的是上面的过程中，也是只有从stack中弹出数据的时候才可以打印。
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class TreeToSequence {
public:
vector<vector<int> > convert(TreeNode* root) {
// write code here
vector<vector<int>> lastresult;
//首先是先序遍历
vector<int> result;
TreeNode* current=root;
stack<TreeNode*> temp;
temp.push(current);
while(!temp.empty()){
current=temp.top();
temp.pop();
result.push_back(current->val);
if(current->right!=NULL)
temp.push(current->right);
if(current->left!=NULL)
temp.push(current->left);
}
lastresult.push_back(result);
//然后是中序遍历
vector<int> result1;
current=root;
while(!temp.empty())
temp.pop();//temp需要清空,注意栈的清空不可以用clear。
while(current!=NULL||!temp.empty()){//这个条件非常重要，之所以为||是因为，初始时current不为空，但是temp为空；下面的过程中，经常current为空，但是temp不为空！！！
while(current!=NULL){
temp.push(current);
current=current->left;
}
current=temp.top();
result1.push_back(current->val);
temp.pop();
current=current->right;
}
lastresult.push_back(result1);
//最后是后序遍历,后序遍历需要定义三个变量，一个是栈，一个是当前栈的栈顶节点，一个是刚刚最近遍历过的节点
vector<int> result2;
TreeNode* pre=root;//pre代表最近遍历过的节点,注意这里的初值一定是root，不可以空NULL。因为假如root的左子树不为空，但是右子树为空的话，如果pre一开始为NULL
//那么下面while循环中的第一个循环就进不去，因为temp.top()->right==pre空，因此左孩子虽然还没有被遍历，但是也进不了栈！！！会导致左孩子遍历不到。
//TreeNode* top=root;//代表当前栈的栈顶节点
while(!temp.empty())
temp.pop();//temp需要清空,注意栈的清空不可以用clear。
temp.push(root);//初始时栈的栈顶节点是root
while(!temp.empty()){
if(temp.top()->left!=NULL&&temp.top()->left!=pre&&temp.top()->right!=pre){//说明top的左子树还没有被处理过
temp.push(temp.top()->left);//将左孩子入栈
}else if(temp.top()->right!=NULL&&temp.top()->right!=pre){//说明top的右孩子没有被处理过
temp.push(temp.top()->right);
}else{//说明top的左右子树为空或者左右子树都已经被遍历过了
result2.push_back(temp.top()->val);
pre=temp.top();
temp.pop();
}
}
lastresult.push_back(result2);
return lastresult;
}
};
对于上面的程序来说，一定更要记住过程！！！并且stack的清空是不可以使用clear的，vector可以用clear进行清空！！！
不管是递归方法还是非递归方法，遍历整颗树的时间复杂度都是o（n）,n为二叉树的节点数，额外空间复杂度为o（l）,l为二叉树的层数。