The problem becomes more difficult once the binary tree is not perfect. The idea is still similar to use a level-order traversal. Note that we do not need to maintain a queue for the traversal becase the next pointer has provided us with the required information.
The following code is taken from the last answer of this link, which is concise and clean. The use of a dummy node simplifies the code. You may play with the code on some examples to see how it works.
1 class Solution { 2 public: 3 void connect(TreeLinkNode *root) { 4 TreeLinkNode* dummy = new TreeLinkNode(0); 5 dummy -> next = root; 6 while (dummy -> next) { 7 TreeLinkNode* pre = dummy; 8 TreeLinkNode* cur = dummy -> next; 9 pre -> next = NULL; 10 while (cur) { 11 if (cur -> left) { 12 pre -> next = cur -> left; 13 pre = pre -> next; 14 } 15 if (cur -> right) { 16 pre -> next = cur -> right; 17 pre = pre -> next; 18 } 19 cur = cur -> next; 20 } 21 } 22 } 23 };
