栈和队列：中序遍历一个二叉树

中序遍历一个二叉树

题目：两种方式遍历给定二叉树

方法一：递归

本方法代码很简单，可见算法的精髓就在于很巧妙的解决问题，并不需要很复杂的代码。

void InOrder(TreeNode *root)
{if(root == NULL)return;InOrder(root->left);visit(root);InOrder(root->right);
}

方法二：用stack临时存储

前言：用stack解决Top-Down结构的问题

所谓的Top-Down结构，从逻辑理解的角度来看，实际上就是一种树形结构，从

顶层出发，逐渐向下扩散，例如二叉树的周游问题。在实际运算的时候，我们

先解决子问题，再利用子问题的结果解决当前问题。

由于Stack的LIFO特性，可以利用Stack数据结构消除递归。Recursion通常用函数

调用自身来实现，在调用的时候系统会分配额外的空间，并且需要用指针记录返回位置，故overhead比较大。

vector<int> InOrder(TreeNode *root)
{vector<int>       output;stack<TreeNode*>  helper;if(root == NULL)return output;while(!helper.empty() || root){if(root){helper.push(root);root = root->left;}else{root = helper.top();helper.pop();output.push(root->val);root = root->right;}}return output;
}