//二叉树的先序递归

ArrayList<Integer> list =new ArrayList<Integer>();

//先序递归遍历

public ArrayList<Integer> preorderTraversal(TreeNode root) {

if(root!=null){

list.add(root.val);

preorderTraversal(root.left);

preorderTraversal(root.right);

}

return list;

}

// 先序非递归遍历

public ArrayList<Integer> preorderTraversal(TreeNode root)

{

Stack<TreeNode> stack=new Stack<TreeNode>();

stack.push(root);

ArrayList<Integer> list=new ArrayList<Integer>();

while(!stack.isEmpty())

{

ListNode ln = stack.pop();

list.add(ln.val);

if(ln.right!=null)

{

stack.push(ln.right);//先push到栈里面的后弹出，所以先序遍历要先push右子树节点

}

if(ln.left!=null)

{

stack.push(ln.left);

}

}

return list;

}