实现二叉树前序中序后序遍历(Java)

import java.util.*;

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

public class Solution {
    /**
     * 
     * @param root TreeNode类 the root of binary tree
     * @return int整型二维数组
     */
    // 递归版(迭代法在后面)
    ArrayList<Integer> list = new ArrayList<>();
    public int[][] threeOrders (TreeNode root) {
        // write code here
        if(root == null){
            return null;
        }
        preOrder(root);
        int[] pre = listToIntArray(list);
        inOrder(root);
        int[] in = listToIntArray(list);
        lastOrder(root);
        int[] last = listToIntArray(list);
        int [][] result = {pre,in,last};
        return result;
    }
    public  int[] listToIntArray(ArrayList<Integer> list){
        int[] result = new int[list.size()];
        for(int i = 0;i<list.size();i++){
            result[i] = list.get(i);
        }
        list.clear();
        return result;
    }
    public  void preOrder(TreeNode root){
        //递归
         if(root!=null){
            list.add(root.val);
            preOrder(root.left);
            preOrder(root.right);
        }
    }
    
    public  void inOrder(TreeNode root){
        //递归
        if(root!=null){
            inOrder(root.left);
            list.add(root.val);
            inOrder(root.right);
        }
    }
    public  void lastOrder(TreeNode root){
        //递归
        if(root!=null){
            lastOrder(root.left);
            lastOrder(root.right);
            list.add(root.val);
        }
    }
}

public class Solution {
    /**
     * 
     * @param root TreeNode类 the root of binary tree
     * @return int整型二维数组
     */
    //迭代法
    ArrayList<Integer> list = new ArrayList<>();
    public int[][] threeOrders (TreeNode root) {
        // write code here
        if(root == null){
            return null;
        }
        preOrder(root);
        int[] pre = listToIntArray(list);
        inOrder(root);
        int[] in = listToIntArray(list);
        lastOrder(root);
        int[] last = listToIntArray(list);
        int [][] result = {pre,in,last};
        return result;
    }
    public  int[] listToIntArray(ArrayList<Integer> list){
        int[] result = new int[list.size()];
        for(int i = 0;i<list.size();i++){
            result[i] = list.get(i);
        }
        list.clear();
        return result;
    }
    public  void preOrder(TreeNode root){
        //利用栈迭代
        /*1.根节点入栈
          2.当栈非空时，栈顶出栈，把出栈的节点值添加到list结尾，然后依次再入栈其右子节点和左子节点
        */
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode curr = stack.pop();
            list.add(curr.val);
            if(curr.right!=null){
                stack.push(curr.right);
            }
            if(curr.left!=null){
                stack.push(curr.left);
            }
        }
    }
    
    public  void inOrder(TreeNode root){
        /*  1.根节点入栈
            2.初始化curr为root
            3.当栈非空或curr非null时，循环
                3.1 cur != null时，说明还有左子节点存在，入栈，并且cur置为自己的左子节点
                3.2 cur == null时，说明到树最左的节点了，栈顶节点出栈，cur置为栈顶节点的右子节点
        */
        Stack<TreeNode> stack = new Stack<>();
        TreeNode curr = root;
        while(!stack.isEmpty()||curr!=null){
            if(curr!=null){
                stack.push(curr);
                curr = curr.left;
            }else{
                //如果curr==null  代表向左遍历到头了 或者刚弹出的元素无右孩子
                //弹出栈顶元素 入列(或打印) 然后向右
                curr = stack.pop();
                list.add(curr.val);
                curr = curr.right;
            }
        }
    }
    public  void lastOrder(TreeNode root){
        //前序遍历的反操作
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode curr = stack.pop();
            list.add(0,curr.val);
            if(curr.left!=null){
                stack.push(curr.left);
            }
            if(curr.right!=null){
                stack.push(curr.right);
            }
        }
    }
}

实现二叉树前序中序后序遍历(Java)

原文：https://www.cnblogs.com/chyEric/p/14310129.html