二叉树先（中后）序非递归版

/*先序遍历非递归方式
定义一个栈，将头节点压入栈中，当栈不为空时，弹出栈顶元素并保存在list中，依次压入右节点和左节点
 */
public static List<Integer> preorderTraversal(TreeNode root){
    List<Integer> res = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    if (root != null) {
        stack.push(root);
        while (!stack.empty()) {
            TreeNode treeNode = stack.pop();
            res.add(treeNode.val);
            if (treeNode.right != null) {
                stack.push(treeNode.right);
            }
            if (treeNode.left != null) {
                stack.push(treeNode.left);
            }
        }
    }
    return res;
}

/*中序遍历非递归方式
定义一个栈，将二叉树的左节点不断压入直到左节点不存在，然后依次弹出栈顶元素值并保存在list中，并切换到右子树
 */
public static List<Integer> inorderTraversal(TreeNode head){
    ArrayList<Integer> res = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    while (head != null || !stack.empty()) {
        if (head != null) {
            stack.push(head);
            head = head.left;
        }
        else{
            head = stack.pop();
            res.add(head.val);
            head = head.right;
        }
    }
    return res;
}

/*后续遍历非递归方式
定义两个栈，当头节点不为空时，将头节点压入s1栈中，在栈s1不为空的循环体中，将s1栈顶节点弹出放入s2中，并将s1的左右节点依次压入到
s1中，最后依次将s2中的节点值弹出保存到list中即为后序遍历的结果。
 */
public static List<Integer> postorderTraversal(TreeNode head){
    ArrayList<Integer> res = new ArrayList<>();
    Stack<TreeNode> s1 = new Stack<>();
    Stack<TreeNode> s2 = new Stack<>();
    if (head != null) {
        s1.push(head);
        while (!s1.empty()) {
            TreeNode treeNode = s1.pop();
            s2.push(treeNode);
            if (treeNode.left != null) {
                s1.push(treeNode.left);
            }
            if (treeNode.right != null) {
                s1.push(treeNode.right);
            }
        }
        while (!s2.empty()){
            res.add(s2.pop().val);
        }
    }
    return res;
}

二叉树先（中后）序非递归版

原文：https://www.cnblogs.com/liuzulong/p/14091091.html