注：本文来自 左程云的书《程序员代码面试指南》
题目：
分别用递归和非递归方法，实现二叉树的先序遍历(根左右)、中序遍历(左根右)、后序遍历(左右根)。
// 二叉树节点
class Node {
public int value;
public Node left;
public Node right;
public Node(int value) {
this.value = value;
}
}
1、递归方式Recursion
（1）先序遍历
public void preOrderRecur(Node root) {
if(root == null) {
return;
}
//先输出根节点的值
System.out.println(root.value + " ");
//递归左子树
preOrderRecur(root.left);
//递归右子树
preOrderRecur(root.right);
}
（2）中序遍历
public void inOrderRecur(Node root) {
if(root == null) {
return;
}
inOrderRecur(root.left);
System.out.println(root.value + " ");
inOrderRecur(root.right);
}
（3）后序遍历
public void posOrderRecur(Node root) {
if(root == null) {
return;
}
posOrderRecur(root.left);
posOrderRecur(root.right);
System.out.println(root.value + " ");
}
2、非递归方式UnRecursion
使用自定义的栈来代替递归栈。
（1）先序遍历
public void preOrderUnRecur(Node root) {
if(root != null) {
Node curNode = root; //当前节点
Stack<Node> stack = new Stack<>(); //辅助栈
stack.add(root);
while(!stack.isEmpty()) {
curNode = stack.pop();
System.out.println(curNode.value + " ");
if(curNode.right != null) {
stack.push(curNode.right);
}
if(curNode.left != null) {
stack.push(curNode.left);
}
}
}
}
（2）中序遍历
public void inOrderUnRecur(Node root) {
if(root != null) {
Node curNode = root; //当前节点
Stack<Node> stack = new Stack<>(); //辅助栈
while(!stack.isEmpty() || curNode != null) {
if(curNode != null) {
stack.push(curNode);
curNode = curNode.left;
}
else {
curNode = stack.pop();
//输出
System.out.println(curNode.value + " ");
curNode = curNode.right;
}
}
}
}
（3）后序遍历
方法一：使用 两个 辅助栈
public void posOrderUnRecur(Node root) {
if(root != null) {
Node curNode = root; //当前节点
Stack<Node> stack1 = new Stack<>();
Stack<Node> stack2 = new Stack<>();
stack1.push(curNode);
while(!stack1.isEmpty()) {
curNode = stack1.pop();
stack2.push(curNode);
if(curNode.left != null) {
stack1.push(curNode.left);
}
if(curNode.right != null) {
stack1.push(curNode.right);
}
}
//弹出stack2中所有元素
while(!stack2.isEmpty()) {
System.out.println(stack2.pop().value + " ");
}
}
}
方法二：使用一个辅助栈
//TODO
