import java.util.*;
/**
* 二叉树定义
* */
class TreeNode{
int val;
TreeNode left;
TreeNode right;
TreeNode(){}
TreeNode(int val){this.val = val}
TreeNode(int val, TreeNode left, TreeNode right){
this.val = val;
this.left = left;
this.right = right;
}
}
class TreeNodeSolution {
//前序遍历 中-左-右 入栈顺序：中-右-左
public List preorder(TreeNode root){
List result =new ArrayList<>();
if (null == root){
return result;
}
Stack stack =new Stack<>();
stack.push(root);
while (!stack.isEmpty()){
TreeNode node = stack.pop();
result.add(node.val);
if (null != node.right){
stack.push(node.right);
}
if (null != node.left){
stack.push(node.left);
}
}
return result;
}
//中序遍历：左-中-右 入栈顺序： 左-右
public List midorder(TreeNode root){
List result =new ArrayList<>();
if (null == root){
return result;
}
Stack stack =new Stack<>();
TreeNode cur = root;
while (!stack.isEmpty() || cur !=null){
if (cur !=null){
stack.push(cur);
cur = cur.left;
}else{
cur = stack.pop();
result.add(cur.val);
cur = cur.right;
}
}
return result;
}
//后序遍历 左-右-中 入栈顺序：左-右-中 出栈顺序：中-右-左 最后反转
public List suforder(TreeNode root){
List result =new ArrayList<>();
if (null == root){
return result;
}
Stack stack =new Stack<>();
stack.push(root);
while (!stack.isEmpty()){
TreeNode node = stack.pop();
result.add(node.val);
if (null != node.left){
stack.push(node.left);
}
if (null != node.right){
stack.push(node.right);
}
}
Collections.reverse(result);
return result;
}
