先序周遊二叉樹

遞歸方式先序周遊二叉樹：

周遊順序：根，左，右

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;
    }