[LeetCode] 145. Binary Tree Postorder Traversal

轉自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>

binary tree traversal 相關問題，這次是要用 postorder : left -> right -> root

一樣使用 iterative 的方式

想法上和 preoder 差不多，但是因為 root 放到最後面去

所以要多一個 node 來記錄某 node 的 child 是否都被訪問過了

code 如下

那當然也可以使用 Morris Traversal，來將空間使用度變成O(1)

但必須修正一下原本的 morris traversal

• 多用一個 dummy head，並把原本的 tree 放到左邊

• output 的地方，改成統一在 left nodes 都跑完後，用 reverse 的方式，將 node 印出來