[数据结构与算法]使用栈实现二叉树三种遍历（第二版）

使用比较统一迭代方法实现三种遍历

$1.$ 在学习《代码随想录》看到的一种方法，可以严格保持三种遍历顺序的入栈顺序；
$2.$ 前序遍历顺序：中左右；入栈顺序：右中左；
$3.$ 中序遍历顺序：左中右；入栈顺序：右中左；
$4.$ 后序遍历顺序：左右中；入栈顺序：中右左；
$5.$ 该方法将“中结点”push入栈后，会push一个null进栈作为标记待pop。

class Solution {
	//前序
    public List<Integer> preorder(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        Stack<TreeNode> st = new Stack<>();
        if (root != null) st.push(root);
        while (!st.empty()) {
            TreeNode node = st.peek();
            if (node != null) {
                st.pop(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中
                if (node.right!=null) st.push(node.right);  // 右
                if (node.left!=null) st.push(node.left);    // 左
                st.push(node);                          // 中
                st.push(null); // 中节点访问过，但是还没有处理，加入空节点做为标记。
                
            } else { // 只有遇到空节点的时候，才将下一个节点放进结果集
                st.pop();           // 将空节点弹出
                node = st.peek();    // 重新取出栈中元素
                st.pop();
                result.add(node.val); // 加入到结果集
            }
        }
        return result;
    }
    //中序
    public List<Integer> midorder(TreeNode root) {
        List<Integer> result = new LinkedList<>();
    Stack<TreeNode> st = new Stack<>();
    if (root != null) st.push(root);
    while (!st.empty()) {
        TreeNode node = st.peek();
        if (node != null) {
            st.pop(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中
            if (node.right!=null) st.push(node.right);  // 右
            st.push(node);                          // 中
            st.push(null); // 中节点访问过，但是还没有处理，加入空节点做为标记。
            if (node.left!=null) st.push(node.left);    // 左
        } else { // 只有遇到空节点的时候，才将下一个节点放进结果集
            st.pop();           // 将空节点弹出
            node = st.peek();    // 重新取出栈中元素
            st.pop();
            result.add(node.val); // 加入到结果集
        	}
    	}
    return result;
	}
	//后序
	public List<Integer> postorder(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        Stack<TreeNode> st = new Stack<>();
        if (root != null) st.push(root);
        while (!st.empty()) {
            TreeNode node = st.peek();
            if (node != null) {
                st.pop(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中
                st.push(node);                          //中
                st.push(null); // 中节点访问过，但是还没有处理，加入空节点做为标记。
                if (node.right!=null) st.push(node.right);  // 右
                if (node.left!=null) st.push(node.left);    // 左
            } else { // 只有遇到空节点的时候，才将下一个节点放进结果集
                st.pop();           // 将空节点弹出
                node = st.peek();    // 重新取出栈中元素
                st.pop();
                result.add(node.val); // 加入到结果集
            }
        }
        return result;
   }
}