二叉树前序、中序、后序遍历非迭代解法-蒲公英云

二叉树前序、中序、后序遍历非迭代解法

经常会有面试官，让你手撕二叉树的前序、中序、后序遍历，当你简单得写了递归的方法，

面试官看了看，慢悠悠得抛出你会迭代的解法吗？，这时候就需要阅读我这篇文章了。

前序和中序遍历，解决方法类似，都是使用栈解决的。后序遍历稍微复杂一点。

二叉树前序遍历

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

二叉树中序遍历

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

二叉树后序遍历

class Solution { 
    public List<Integer> postorderTraversal(TreeNode root) { 
        ArrayList<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        if(root != null) stack.push(root);
        while(!stack.empty()) { 
            TreeNode value = stack.pop();
            list.add(value.val);
            if(value.left != null) stack.push(value.left);
            if(value.right != null) stack.push(value.right);
        }
        ArrayList<Integer> result = new ArrayList<>();
        for(int i = list.size()-1; i >= 0; i--) result.add(list.get(i));
        return result;
    }
}