LeetCode之後序疊代周遊

問題描述：

/**
 * Given a binary tree, return the postorder traversal of its nodes' values.
 *
 * For example:
 * Given binary tree {1,#,2,3},
 *   1
 *    \
 *     2
 *    /
 *   3
 * return [3,2,1].
 *
 * Note: Recursive solution is trivial, could you do it iteratively?
 * 
 * Solution:
 * 
 * 1. Root - Right - Left
 * 2. Then reverse the sequence
 * 3. Left - Right - Root
 *
 */
           

在後序非遞歸周遊時，要借助棧的操作，由于棧是先進後出，是以在後序周遊時要先壓入右孩子，這樣才能保證在棧的彈出操作時會優先彈出左孩子。

public class BinaryTreePostorderTraversal {
     public static ArrayList<Integer> postorderTraversal(TreeNode root) {
            ArrayList<Integer> ret = new ArrayList<Integer>();
            if (root == null)
                return ret;
            Stack<TreeNode> st = new Stack<TreeNode>();
            TreeNode p = root.right;
            ret.add(root.val);
            st.add(root);
            while (!st.isEmpty()) {
                while (p != null) {
                    ret.add(p.val);
                    st.add(p);
                    p = p.right;
                }
                TreeNode node = st.pop();
                p = node.left;
                if (p != null) {
                    ret.add(p.val);
                    st.add(p);
                    p = p.right;
                }
            }
            int i = ;
            int j = ret.size() - ;
            while(i < j) {//數組逆置就得到後序周遊的結果
                int tmp = ret.get(i);
                ret.set(i, ret.get(j));
                ret.set(j, tmp);
                i++;
                j--;
            }
            return ret;
        }
    //測試代碼
        public static void main(String arg[])
        {
            TreeNode r1 = new TreeNode();  
            TreeNode r2 = new TreeNode();  
            TreeNode r3 = new TreeNode();  
            TreeNode r4 = new TreeNode();
            TreeNode r5 = new TreeNode();
            TreeNode r6 = new TreeNode();
            r1.left = r2;  
            r1.right = r3;  
            r2.left=r4;
            r3.right=r5;
            r3.left=r6;
            ArrayList<Integer> array=postorderTraversal(r1);
            for(int i=;i<array.size();i++)
            {
                System.out.print(array.get(i)+",");
            }

        }
}