二叉树的中序遍历（递归和非递归）

前一篇文章中已经写过二叉树的先序遍历了，这一篇我们继续探究二叉树的中序遍历。
中序遍历（LDR）是二叉树树中遍历的一种，也称之为中根遍历、中序周游。在二叉树中，先左后根再右。记为：左根右。

该完全二叉树中序遍历的结果为：7, 3, 8, 1, 9, 4, 0, 5, 2, 6
⼆叉树的中序遍历顺序是左-根-右。采⽤⼀个栈来辅助，我们把中序遍历的结果放到⼀个ArrayList 容器中作为返回值，具体步骤如下：
1、进⼊ while 循环，接着把根节点及其所有左⼦节点放⼊栈中。
2、遍历完左子节点后，从棧中弹出节点，把节点存入list中；如果该节点的右⼦节点不为空，则把右⼦节点及其右⼦节点的所有左⼦节点放⼊棧中。
3、⼀直重复步骤 2 ，直到栈为空并且当前节点也为空则退出循环。
代码实现如下：

public static List<Integer> inOderTraversal(TreeNode root){
		List<Integer> result = new ArrayList<Integer>();
		Stack<TreeNode> stack = new Stack<TreeNode>();
		while(root!=null || !stack.isEmpty()) {
			if(root!=null) {
				stack.push(root);
				root = root.left;
			}
			else {
				root = stack.pop();
				result.add(root.value);
				root = root.right;
			}
		}
		return result;
	}
	public static void inOderTre(TreeNode root) {
		//中序遍历的递归方法
		if(root == null) {
			return;
		}
		else {
			inOderTre(root.left);
			System.out.println(root.value);
			inOderTre(root.right);
		}
		
	}