二叉树的前序遍历

递归写法

public int[] preorderTraversal (TreeNode root) {
        // write code here
        List<Integer> list=new ArrayList<Integer>();
        dfs(list,root);
        int[] res=new int[list.size()];
        for (int i=0;i<list.size();i++){
            res[i]=list.get(i);
        }
        return res;
    }
    public void dfs(List<Integer> list,TreeNode root){
        if(root==null) return;
        list.add(root.val);
        dfs(list,root.left);
        dfs(list,root.right);
    }

非递归写法 前序遍历使用栈，但栈是先进后出，所以需要先使右节点进栈。 之后进行遍历。

 public int[] preorderTraversal (TreeNode root) {
        // write code here
        if(root==null) return new int[0];
        Deque<TreeNode> stack=new LinkedList<TreeNode>();
        List<Integer> list=new ArrayList<Integer>();
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode node=stack.pop();
            list.add(node.val);
            if(node.right!=null){
                stack.push(node.right);
            }
            if(node.left!=null){
                stack.push(node.left);
            }
        }
        int[] res=new int[list.size()];
        for (int i=0;i<list.size();i++){
            res[i]=list.get(i);
        }
        return res;
    }