[LeetCode] 94. Binary Tree Inorder Traversal

轉自LeetCode

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

For example:
Given binary tree [1,null,2,3],

   1
    \
     2
    /
   3

return [1,3,2].

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

<Solution>

這題是要做 inorder 的 traversal，一樣只使用 iterative 的方式

還是多用一個 stack 來幫忙，按照 inorder traversal 的方式塞到 stack 就好

code 如下

這邊再多看一個時間複雜度O(n)，空間複雜度為 O(1) 的 inorder traversal 方式

意即不用再多一個 stack 的方式

叫做 Morris Traversal，這種方式會用到一個資料結構叫 threaded tree

想法如下

• curr 一開始指向 root

• curr 不是 NULL 的話，重複以下步驟

• 如果 curr 沒有左節點

• 輸出 curr->val

• curr 指向右節點

• 如果 curr 有左節點

• 在左子樹裡面找到最右節點

• 如果最右節點的 right = NULL，將 right = curr，代表 curr 是最右節點的 predecessor(此右節點結束後，回到 curr)

• 如果最右節點 right != NULL，代表 curr 的所有左節點都完成的，按照 inorder 的順序(left -> root -> right)，此時就是輸出 curr->val，然後把 curr = curr->right

code 如下