面试常考算法题之二叉树的先序遍历

//面试常考算法题之二叉树的先序遍历
public class Solution
{
	public List preorder(TreeNode root){
		List res=new ArrayList<>();
		recur(root,res);
		return res;
	}
	//递归版
	public void recur(TreeNode root,List res){
		if(root==null) return;
		list.add(root.val);
		recur(root.left,res);
		recur(root.right,res);
	}
}



public class Solution

{
        //迭代
	public List preorder(TreeNode root){
		Deque stack=new LinkedList<>();
		List list=new ArrayList<>();
		TreeNode cur=root;
		while(!stack.isEmpty()||cur!=null){
			if(cur!=null){
				list.add(cur.val);
				stack.push(cur);
				cur=cur.left;
			}
			cur=stack.pop().righgt;
		}
		return list;
	} 
}