[LeetCode] 114. Flatten Binary Tree to Linked List

轉自LeetCode

Given a binary tree, flatten it to a linked list in-place.

For example,
Given

         1
        / \
       2   5
      / \   \
     3   4   6

The flattened tree should look like:

   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6

Hints:

If you notice carefully in the flattened tree, each node's right child points to the next node of a pre-order traversal.

<Solution>

這題是要把 binary tree 變成一個 flattened tree

也就是所有的 node 都是用 right node 給串起來

這邊解題想法是修改原本的 morris inorder traversal，過程如下 (參考資料)

code 如下

再來看一個 recursive 的解法

• 先從左子樹下手，把左子樹都 flatten

• 然後 flatten 右子樹

• 合併左右子樹

• recursive 重複前面的步驟

code 如下