题解 | #二叉树的遍历#

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整型二维数组
     */
    public int[][] threeOrders (TreeNode root) {
        if(root == null) {
            return new int[3][0] ;
        }
        List<Integer> l1 = pre(root) ;
        List<Integer> l2 = in(root) ;
        List<Integer> l3 = post(root) ;
        int[][] res = new int[3][l1.size()] ;
        for(int i = 0 ; i < l1.size() ; i ++) {
            res[0][i] = l1.get(i) ;
        }
        for(int i = 0 ; i < l2.size() ; i ++) {
            res[1][i] = l2.get(i) ;
        }
        for(int i = 0 ; i < l3.size() ; i ++) {
            res[2][i] = l3.get(i) ;
        }
        return res ;
    }
    public List<Integer> pre(TreeNode root) {
        List<Integer> res = new ArrayList<>() ;
        Stack<TreeNode> st = new Stack() ;
        TreeNode t = root ;
        st.push(t) ;
        while(!st.isEmpty()) {
            t = st.pop() ;
            res.add(t.val) ;
            if(t.right != null) {
                st.push(t.right) ;
            }
            if(t.left != null) {
                st.push(t.left) ;
            }
        }
        return res;
    }
    public List<Integer> in(TreeNode root) { 
        List<Integer> res = new ArrayList<>() ;
        Stack<TreeNode> st = new Stack() ;
        TreeNode t = root ;
        while(t != null || !st.isEmpty()) {
            if(t != null) {
                st.push(t) ;
                t = t.left ;
            } else {
                t = st.pop() ;
                res.add(t.val) ;
                t = t.right ;
            }
            
        }
        return res ;
    }
    public List<Integer> post(TreeNode root) { 
        List<Integer> res = new ArrayList<>() ;
        Stack<TreeNode> st = new Stack() ;
        Stack<TreeNode> st1 = new Stack() ;
        TreeNode t = root ;
        st.push(t) ;
         while(!st.isEmpty()) {
            t = st.pop() ;
             st1.push(t) ;
            if(t.left != null) {
                st.push(t.left) ;
            }
            if(t.right != null) {
                st.push(t.right) ;
            }
             
        }
        while(!st1.isEmpty()) {
            res.add(st1.pop().val) ;
        }
        return res ;
    }
}