层次遍历二叉树的变种

还是回归到ITEYE，之前想用CSDN的，但是受不了那个的响应速度，估计是太多的访问量了，好，废话少说，今天记录一下一朋友面试时候遇到的问题

 

问题描述如图：

 具体说明：现在有一颗二叉树，如图中红线所示，现在需要将该二叉树按照黑色箭头的方式遍历

题目描述很简单，也算是一个层次遍历的变种问题，我们知道，在层次遍历里面使用的是队列保存其子节点，但是在这道题里面显然是不能够的，因为访问的方向不一致，我们可以想到，因为上图的遍历方式和我们日常用到的层次遍历正好相反，因此我们考虑使用栈这一个特殊的结构来解决问题

 

首先考虑使用一个栈，我们读到一个根节点后就依次把左子节点和右子节点放入到栈中，下次遍历的时候取出栈的栈首就行了，于是考虑成：

 
 

 如上图，当根节点访问之后，一次将其左右子节点入栈，下次访问的是3号节点，但是3号节点访问完之后就会出现问题了，因为只要三号节点的子节点一入栈，整个遍历的顺序就不能是按照要求了，栈的结构会出现上图所示的的右边情形，这显然不符合要求

 

因此，在这种结构下，由于每次访问顺序都会改变一下，因此可以考虑使用两个栈来进行操作，据图说明如下图：

 

 如上图所示，这样就可以实现要求的遍历方式了

 

好了现在可以实现代码了，代码中为了验证我们建立的二叉树是正确的，所以最后写了一个前序遍历来验证二叉树建立的正确性，代码如下

#include<iostream>
#include<stack>
using namespace std;
/*

Author :luchi
Date:2015/10/28

TestCase: 1 2  -1  4 -1 -1 3 -1 5 6 -1 -1 7 -1 -1 

notes:这里使用前序遍历的方式构建二叉树，-1表示是空节点，用来递归返回使用，按照上述的输入序列即可得到题目图所描述的二叉树 

*/ 



//定义结构体 
struct TreeNode{
	
	TreeNode(){
		leftChild=NULL;
		rightChild=NULL; 
		num=0;
	}
	int num;
	TreeNode* leftChild;
	TreeNode* rightChild;
};
TreeNode * root;


//注意这里的&很重要 
void buildBinaryTree(TreeNode* &root){
	
	int num;
	cin>>num;
	if(num==-1){
		root=NULL;
		return ;
	}
	root->num=num;
	root->leftChild=new TreeNode();
	buildBinaryTree(root->leftChild);
	root->rightChild=new TreeNode();
	buildBinaryTree(root->rightChild);
	
}

//给定的层次遍历 ，按照图示所说进行 
void levelScanWithDoubleStack(TreeNode* root){
	
	stack<TreeNode*> stackA;
	stack<TreeNode*> stackB;
	bool flag=true;
	stackA.push(root);
	while(!stackA.empty() || !stackB.empty()){
		if(flag){
			while(!stackA.empty()){
				TreeNode* newRoot=stackA.top();
				cout<<newRoot->num<<"  ";
				if(newRoot->leftChild!=NULL){
					stackB.push(newRoot->leftChild);
				}
				if(newRoot->rightChild!=NULL){
					stackB.push(newRoot->rightChild);
				}
				stackA.pop();
			}
			flag=false;
		}else{
			while(!stackB.empty()){
				TreeNode* newRoot=stackB.top();
				cout<<newRoot->num<<"  ";
				if(newRoot->leftChild!=NULL){
					stackA.push(newRoot->leftChild);
				}
				if(newRoot->rightChild!=NULL){
					stackA.push(newRoot->rightChild);
				}
				stackB.pop();
			}
			flag=true;
		}
	}
}
void preScan(TreeNode* root) {
	if(root!=NULL){
		cout<<root->num<<"  ";
		preScan(root->leftChild);
		preScan(root->rightChild);
	}
}
int main(){

	
	root=new TreeNode();
	buildBinaryTree(root);
	cout<<"前序遍历结果是："<<endl;
	preScan(root) ;
	cout<<endl; 
	cout<<"最后的遍历结果是 "<<endl; 
	levelScanWithDoubleStack(root);
	return 0;	
} 

 结果如图：

1 2  -1  4 -1 -1 3 -1 5 6 -1 -1 7 -1 -1
前序遍历结果是：
1  2  4  3  5  6  7
最后的遍历结果是
1  3  2  4  5  7  6

 当然，选择建立二叉树的方式有很多，比如建立比较二叉树，等等之类，只是前序递归建立二叉树比较方便简单，不用每次插入节点都去遍历整棵树，因为本题的要点不是在二叉树上，所以选择了一个最简单的方式。