145. Binary Tree Postorder Traversal

Link

難易度 : Easy

這題建議搭配preorder-144、inorder-94一起寫會很有感覺。
題目是二元樹基本的三種遍尋的操作，這邊附上各篇連結

1. preorder 144
2. inorder 94
3. postorder 145

一開始同樣是最簡單的recursive的作法

    //recursively
    class Solution
    {
        public List<Integer> postorderTraversal(TreeNode root)
        {
            List<Integer> list = new ArrayList<Integer>();
            PostorderTree(root,list);
            return list;
        }

        private void PostorderTree(TreeNode current,List<Integer> list) 
        {
            if(current==null) 
            {
                return;
            }
            PostorderTree(current.left,list);
            PostorderTree(current.right,list);
            list.add(current.val);
        }
    }

並且依照題目要求，可以接著以iteratively的作法來實作，基本的觀念同樣是使用stack來實現recursive

整體的作法其實不難理解，其實最關鍵的一點就是

postorder就是preorder的reverse!

那麼想通之後作法就很簡單了

    //iteratively
    class Solution
    {
        public List<Integer> postorderTraversal(TreeNode root)
        {
            List<Integer> list = new ArrayList<Integer>();
            Stack<TreeNode> stack = new Stack<TreeNode>();
            if(root==null) 
            {
                return list;
            }
            stack.push(root);
            while(!stack.isEmpty()) 
            {
                TreeNode current = stack.pop();
                list.add(current.val);              
                if(current.left!=null) 
                {
                    stack.push(current.left);
                }
                if(current.right!=null) 
                {
                    stack.push(current.right);
                }
            }
            Collections.reverse(list);

            return list;
        }   
    }

同樣的雖然實作出來了，可是還是希望這種類型的題目都能有個統一風格的作法
一樣的利用插入null node來判斷何時該處理紀錄val何時該繼續遍尋

    //common style
    class Solution
    {
        public List<Integer> postorderTraversal(TreeNode root)
        {
            List<Integer> list = new ArrayList<Integer>();
            Stack<TreeNode> stack = new Stack<TreeNode>();
            if(root==null) 
            {
                return list;
            }
            stack.push(root);
            while(!stack.isEmpty()) 
            {
                TreeNode current = stack.pop();
                if(current==null) 
                {
                    current = stack.pop();
                    list.add(current.val);
                }
                else 
                {
                    stack.push(current);
                    stack.push(null);
                    if(current.right!=null) 
                    {
                        stack.push(current.right);
                    }
                    if(current.left!=null) 
                    {
                        stack.push(current.left);
                    }               
                }
            }           
            return list;
        }       
    }

其實這種通用寫法最大的地方就是當碰到不是null的node時，插入current與插入null node這兩件事情是一個整體的，因為這代表著null之後的node是需要被處理的。