注：本文來自 左程云的書《程序員代碼面試指南》

題目：
分別用遞歸和非遞歸方法，實(shí)現(xiàn)二叉樹的先序遍歷(根左右)、中序遍歷(左根右)、后序遍歷(左右根)。
// 二叉樹節(jié)點(diǎn)
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;
    }
    //先輸出根節(jié)點(diǎn)的值
    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;    //當(dāng)前節(jié)點(diǎn)
        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;    //當(dāng)前節(jié)點(diǎn)
        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）后序遍歷
方法一：使用 兩個(gè) 輔助棧
public void posOrderUnRecur(Node root) {

    if(root != null) {
        Node curNode = root;    //當(dāng)前節(jié)點(diǎn)
        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 + " ");
        }
    }
}

方法二：使用一個(gè)輔助棧
//TODO