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

非递归算法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> list1=new ArrayList<Integer>();
ArrayList<Integer> list2=new ArrayList<Integer>();
ArrayList<Integer> list3=new ArrayList<Integer>();
ArrayList<ArrayList<Integer>> res=new ArrayList<>();
public int[][] threeOrders (TreeNode root) {
    // write code here 用递归实现,前序，中序，后续，本次采用非递归方法实现
    
    preOrder(root);
    inOrder(root);
    postOrder(root);
    res.add(list1);
    res.add(list2);
    res.add(list3);
    int[][] ans=new int[3][list1.size()];
    for(int i=0;i<list1.size();i++){
        ans[0][i]=list1.get(i);
        ans[1][i]=list2.get(i);
        ans[2][i]=list3.get(i);
    }
    return ans;
}
public void preOrder(TreeNode root){
    if(root==null) return;
    LinkedList<TreeNode> list=new LinkedList<>();
    TreeNode p=root;
    list.push(p);
    while(list.size()>0){
        p=list.peek();
        list.pop();
        list1.add(p.val);
        if(p.right!=null) list.push(p.right);
        if(p.left!=null) list.push(p.left);
    }
    return;
}
public void inOrder(TreeNode root){
    if(root==null) return;
    LinkedList<TreeNode> list=new LinkedList<>();
    TreeNode p=root;
    while(list.size()>0||p!=null){
        while(p!=null){
            list.push(p);
            p=p.left;
        }
        p=list.peek();
        list2.add(p.val);
        list.pop();
        p=p.right;
    }
    return;
}
public void postOrder(TreeNode root){
    if(root==null) return;
    LinkedList<TreeNode> list=new LinkedList<>();
    TreeNode p=root,last=null;
    while(list.size()>0||p!=null){
        while(p!=null){
            list.push(p);
            p=p.left;
        }
        p=list.peek();
        if(p.right==null||last==p.right){
            list.pop();
            list3.add(p.val);
            last=p;
            p=null;
        }else{
            p=p.right;
        }
   }
   return;
}

}