[LeetCode] 116. Populating Next Right Pointers in Each Node

轉自LeetCode

Given a binary tree

    struct TreeLinkNode {
      TreeLinkNode *left;
      TreeLinkNode *right;
      TreeLinkNode *next;
    }

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Note:

• You may only use constant extra space.
• You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).

For example,
Given the following perfect binary tree,

         1
       /  \
      2    3
     / \  / \
    4  5  6  7

After calling your function, the tree should look like:

         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \  / \
    4->5->6->7 -> NULL

<Solution>

這題就是要把 perfect binary tree 的每個 level 也串起來變成一個 linked list

最直接的想法就是 level-order traversal，過程中同時把同 level 的 node 都 link 起來

code 如下

可是這個解法不符合題目要求，因為題目要求是要 constant extra space

因此，有另一種想法

• 準備兩個指針，一個指向每個 level 最左邊的 node，一個去歷遍在同一 level 的 node

• 每次 iteration，都是將目前 node 的左右子node 給串起來

code 如下(參考資料)