题解 | #实现二叉树先序，中序和后序遍历-循环迭代实现#

• 先序：根左右
• 中序：左根右
• 后序：左右根

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    public int[][] threeOrders (TreeNode root) {
        // write code here
        int[][] arr = new int[3][];
        List<Integer> list = new ArrayList<>();
        
        preorder(root,list);
        arr[0] = listToArray(list);
        list.clear();
        
        inorder(root,list);
        arr[1] = listToArray(list);
        list.clear();

        postorder(root,list);
        arr[2] = listToArray(list);
        list.clear();
        return arr;
    }
    
    public int[] listToArray(List<Integer> list){
        return list.stream().mapToInt(Integer::valueOf).toArray();
    }


    /**
     * 先序遍历的原则是：先根、再左、再右。
     * @param root
     * @param list
     */
    private void preorder(TreeNode root, List<Integer> list){
        Stack<TreeNode> stack = new Stack<>();
        TreeNode tempNode = root;
        while(!stack.isEmpty() || tempNode != null){
            if (tempNode != null) {
                list.add(tempNode.val);
                stack.push(tempNode);
                tempNode = tempNode.left;
            } else {
                tempNode = stack.pop();
                tempNode = tempNode.right;
            }
        }
    }

    /**
     * 中序遍历的原则是：先左、再根、再右
     * @param root
     * @param list
     */
    private void inorder(TreeNode root, List<Integer> list){
        Stack<TreeNode> stack = new Stack<>();
        TreeNode tempNode = root;
        while(!stack.isEmpty() || tempNode != null){
            if (tempNode != null) {
                stack.push(tempNode);
                tempNode = tempNode.left;
            } else {
                tempNode = stack.pop();
                list.add(tempNode.val);
                tempNode = tempNode.right;
            }
        }
    }

    /**
     * 后序遍历的原则是：先左、再右、再根
     * @param root
     * @param list
     */
    private void postorder(TreeNode root, List<Integer> list){
        Stack<TreeNode> stack = new Stack<>();
        TreeNode tempNode = root;
        while (!stack.isEmpty() || tempNode != null) {
            if (tempNode != null) {
                stack.push(tempNode);
                list.add(0, tempNode.val);
                tempNode = tempNode.right;
            } else {
                tempNode = stack.pop();
                tempNode = tempNode.left;
            }
        }
    }
}