import java.util.*;
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}*/
public class TreeToSequence {
public int[][] convert(TreeNode root) {
// write code here
// write code here
List<Integer> pre = new ArrayList<Integer>();
List<Integer> in = new ArrayList<Integer>();
List<Integer> post = new ArrayList<Integer>();
preTraverse(root, pre);
inTraverse(root, in);
postTraverse(root, post);
int[][] result = new int[3][pre.size()];
for(int i = 0; i < pre.size(); i++){
result[0][i] = pre.get(i);
result[1][i] = in.get(i);
result[2][i] = post.get(i);
}
return result;
}
public void preTraverse(TreeNode root, List<Integer> pre){
if(root == null){
return;
}
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(root);
while(!stack.isEmpty()){
TreeNode cur = stack.pop();
pre.add(cur.val);
if(cur.right != null){
stack.push(cur.right);
}
if(cur.left != null){
stack.push(cur.left);
}
}
}
public void inTraverse(TreeNode root, List<Integer> in){
if(root == null){
return;
}
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode cur = root;
while(!stack.isEmpty() || cur != null){
if(cur!= null){
stack.push(cur);
cur = cur.left;
}
else{
cur = stack.pop();
in.add(cur.val);
cur = cur.right;
}
}
}
public void postTraverse(TreeNode root, List<Integer> post){
if(root == null){
return;
}
Stack<TreeNode> stack1 = new Stack<TreeNode>();
Stack<TreeNode> stack2 = new Stack<TreeNode>();
stack1.push(root);
while(!stack1.isEmpty()){
TreeNode cur = stack1.pop();
stack2.push(cur);
if(cur.left != null){
stack1.push(cur.left);
}
if(cur.right != null){
stack1.push(cur.right);
}
}
while(!stack2.isEmpty()){
post.add(stack2.pop().val);
}
}
}
