# 4 java solutions include recursive,morris and two other iterative

• recursive

``````List<Integer> l=new ArrayList<Integer>();
public List<Integer> preorderTraversal(TreeNode root) {
if(root==null) return l;
if(root.left!=null) preorderTraversal(root.left);
if(root.right!=null) preorderTraversal(root.right);
return l;
}
``````

Morris

``````public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> l=new ArrayList<Integer>();
if(root==null) return l;
TreeNode pre,cur=root;
while(cur!=null){
if(cur.left==null){
cur=cur.right;
}else{
pre=cur.left;
while(pre.right!=null&&pre.right!=cur){
pre=pre.right;
}
if(pre.right==null){
pre.right=cur;
cur=cur.left;
}else{
pre.right=null;
cur=cur.right;
}
}
}
return l;
}
``````

Iterative1

``````public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> l=new ArrayList<Integer>();
if(root==null) return l;
Stack<TreeNode> stack=new Stack<TreeNode>();
while(!stack.isEmpty()||root!=null){
if(root!=null){
stack.push(root);
root=root.left;
}else{
root=stack.pop();
root=root.right;
}
}
return l;
}
``````

Iterative2

``````public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> l=new ArrayList<Integer>();
if(root==null) return l;
Stack<TreeNode> stack=new Stack<TreeNode>();
stack.push(root);
while(!stack.isEmpty()){
root=stack.pop();