栈实现中序遍历二叉树

题目描述

算法思想：

1、得到根结点后，若左孩子结点不空，不断地将当前结点的左孩子则入栈，第一步完成后，栈顶结点是叶结点
2、栈不空时，将栈顶元素弹出并保存到返回的答案数组，并查看当前结点是否有右孩子，有则入栈，然后重复步骤1。没有则接着执行步骤2，直到栈空。

	vector<int> ans; //返回的答案数组
	vector<Node*> stack; // vector模拟栈
	vector<int> inorderTraversal(Node* root){
    	if(root == NULL)  return ans;
    	Node* cur = root;  
    	stack.push_back(cur);
    	//首先将所有的左孩子压栈
    	while(cur->lchild != NULL){
        	stack.push_back(cur->lchild);
        	cur = cur->lchild;
    	}
    	//退出循环后cur指向叶结点，准备回溯
    	while(stack.size() > 0){
        	cur = stack[stack.size()-1];
        	ans.push_back(cur->data);
        	stack.pop_back();
        	if(cur->rchild != NULL){
            	stack.push_back(cur->rchild);
            	cur = cur->rchild;
            	while(cur->lchild != NULL){
                	stack.push_back(cur->lchild);
                	cur = cur->lchild;
            	}
        	}
    	}
    	return ans;
}