[LeetCode] 144. Binary Tree Preorder Traversal

轉自LeetCode

Given a binary tree, return the preorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [1,2,3].

Note: Recursive solution is trivial, could you do it iteratively?

<Solution>

題目有要求要用 iterative 的做法，不要用 recursive

那這時候就多用一個 stack 來幫忙

• 第一個當然是把 root 丟進去 stack

• stack 不為空，就一直迴圈

• 拿 top 出來，將其值放到 ans 裡

• 先檢查 right child，有 right child 就放到 stack

• 再檢查 left child，有 left child 就放到 stack

Note: 因為 stack 是 LIFO，且 preorder traversal 的順序是 root->left->right，所以先看right再看left

code 如下

這邊也可以用 morris traversal 來做 preorder traversal

和 inorder traversal 不同的地方只在於輸出順序

因為 inorder 是 left->root->right，preorder 是 root->left->right

所以不用等 left node 都結束再印出 root，而是要先印出來

code 如下