题解 | #实现二叉树先序，中序和后序遍历#

import java.util.*;
import java.lang.*;

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

public class Solution {
     List<Integer> pre = new ArrayList<>();
    List<Integer> in = new ArrayList<>();
    List<Integer> post = new ArrayList<>();
    /**
     * 
     * @param root TreeNode类 the root of binary tree
     * @return int整型二维数组
     */
    public int[][] threeOrders (TreeNode root) {
        // 先序遍历
        preOrderRecur(root);
        // 中序遍历
        inOrderRecur(root);
        // 后序遍历
        postOrderRecur(root);
        int i = 0;
        int[][] res = new int[3][pre.size()];
        while(i < pre.size()){
            res[0][i] = pre.get(i);
            res[1][i] = in.get(i);
            res[2][i] = post.get(i);
            i++;
        }
        return res;
    }
    
    // 先序遍历非递归版
    public void preOrderRecur(TreeNode root){
        if(root!= null){
            Stack<TreeNode> stack = new Stack();
            stack.push(root);
            while(!stack.isEmpty()){
                TreeNode node = stack.pop();
                pre.add(node.val);
                if(node.right!=null){
                    stack.push(node.right);
                }
                if(node.left != null){
                    stack.push(node.left);
                }
            }
        }
    }
    
    // 中序遍历非递归版
    public void inOrderRecur(TreeNode root){
        if(root!= null){
            Stack<TreeNode> stack = new Stack();
            while(!stack.isEmpty() || root != null){
                if(root!=null){
                    stack.add(root);
                    root = root.left;
                }else{
                    TreeNode node = stack.pop();
                    in.add(node.val);
                    if(node.right!=null){
                        root = node.right;
                    }
                }
            }
        }
    }
    
    // 后序遍历非递归版
     public void postOrderRecur(TreeNode root){
        if(root!= null){
            Stack<Integer> help =  new Stack();
            Stack<TreeNode> stack = new Stack();
            stack.add(root);
            while(!stack.isEmpty()){
                TreeNode node = stack.pop();
                help.add(node.val);
                if(node.left != null){
                    stack.add(node.left);
                }
                if(node.right != null){
                    stack.add(node.right);
                }
            }
            while(!help.isEmpty()){
                post.add(help.pop());
            }
        }
    }
    
    public void preOrderRecur1(TreeNode root){
            if(root == null){
                return;
            }
            pre.add(root.val);
            preOrderRecur(root.left);
            preOrderRecur(root.right);
    }
    
    public void inOrderRecur1(TreeNode root){
        if(root == null){
            return;
        }
        inOrderRecur(root.left);
        in.add(root.val);
        inOrderRecur(root.right);
    }
    
     public void postOrderRecur1(TreeNode root){
        if(root == null){
            return;
        }
        postOrderRecur(root.left);
        postOrderRecur(root.right);
         post.add(root.val);
    }
    
}