先序遍历二叉树

递归方式先序遍历二叉树：

遍历顺序：根，左，右

public static List<Integer> preorderTraversal(TreeNode root) {
        if(root == null) return Collections.EMPTY_LIST;
        List<Integer> list = new ArrayList<Integer>();
        list.add(root.val);
        list.addAll(preorderTraversal(root.left));//注意使用List.addAll()方便了很多
        list.addAll(preorderTraversal(root.right));
        return list;
        }
           

public static List<Integer> preorderTraversal(TreeNode root) {

        List<Integer> list = new ArrayList<Integer>();
        if(root == null) return list;
        Stack<TreeNode> st = new Stack<TreeNode>();

        st.push(root);

        while(!st.isEmpty()){
            TreeNode tmp = st.pop();//先遍历的根节点入栈
            list.add(tmp.val);
            if(tmp.right != null) st.push(tmp.right);//由于栈结果是后进先出，所以右节点先入栈，保证左节点先出栈
            if(tmp.left != null) st.push(tmp.left);
        }

        return list;
    }