使用栈来对实现二叉树的非递归遍历

基本思路都是采用对于一棵树将左链压入栈中，出栈，判断节点是否有右儿子，如果存在则循环（作为一棵树为相同子结构进行递归），如果不存在，则会循环到下一次出栈

直到栈为空且节点为空

前序遍历的非递归形式

1. 将当前节点输出
2. 将当前节点的右节点入栈，左节点入栈

LeetCode 144

class Solution {
    Stack<TreeNode> stack = new Stack<>();
    List<Integer> list = new ArrayList<>();
    public List<Integer> preorderTraversal(TreeNode root) {
        if (root == null) return list;
        stack.push(root);
        while (!stack.isEmpty()) {
            root = stack.pop();
            list.add(root.val);
            if (root.right != null) stack.push(root.right);
            if (root.left != null) stack.push(root.left);
        }
        return list;
    }
}

使用左链的形式

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        while (!stack.isEmpty() || root != null) {
            while (root != null) {
                res.add(root.val);
                stack.push(root);
                root = root.left;
            }
            TreeNode top = stack.pop();
            if (top.right != null) root = top.right;
        }
        return res;
    }
}

中序遍历的非递归形式：

1. 将当前节点的左链压入到栈中
2. 将栈顶元素出栈，判断是否存在右节点，存在则重复步骤1

LeetCode 94

class Solution {
    Stack<TreeNode> stack = new Stack<>();
    List<Integer> list = new ArrayList();
    public List<Integer> inorderTraversal(TreeNode root) {
        // 注意添加`root != null`，使得初始满足条件
        while (!stack.isEmpty() || root != null) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            TreeNode top = stack.pop();
            list.add(top.val);
            if (top.right != null) root = top.right;
        }
        return list;
    }
}

后序遍历的非递归形式

1. 将当前节点的左链压入到栈中
2. 判断栈顶元素是否有右节点，且处在向下走的过程中，重复操作1；否则，出栈，更新lastVisitedNode

LeetCode 145

class Solution {
    Stack<TreeNode> stack = new Stack<>();
    List<Integer> list = new ArrayList();
    public List<Integer> postorderTraversal(TreeNode root) {
        TreeNode lastVisitedNode = null;
        while (!stack.isEmpty() || root != null) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            TreeNode topNode = stack.peek();
            if (topNode.right != null && topNode.right != lastVisitedNode) root = topNode.right; 
            else { stack.pop(); list.add(topNode.val); lastVisitedNode = topNode;}
        }
        return list;
    }