[LeetCode] Populating Next Right Pointers in Each Node I, II

Populating Next Right Pointers in Each Node I

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

Populating Next Right Pointers in Each Node II

Follow up for problem "Populating Next Right Pointers in Each Node".

What if the given tree could be any binary tree? Would your previous solution still work?

Note:

• You may only use constant extra space.

For example,
Given the following binary tree,

         1
       /  \
      2    3
     / \    \
    4   5    7

After calling your function, the tree should look like:

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

思路：

能解II的算法必然能解I，所以这里只讨论II的解。

递推：在第i层的所有next pointer都连接好的情况下，如何连接第i+1层的next pointer?
显然从第i层的最左节点开始依次通过next pointer遍历这一层，同时将他们的children，即第i+1层的节点依次通过next pointer连接起来。连接的时候要分情况处理。

初始情况：对于顶层，只有一个节点root，所以该层连接已经完成。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

class Solution { public: void connect(TreeLinkNode *root) { while(root && !root->left && !root->right) root = root->next; if(!root) return; TreeLinkNode *leftMost = root->left ? root->left : root->right; TreeLinkNode *cur = leftMost; while(root) { if(cur==root->left) { if(root->right) { cur->next = root->right; cur = cur->next; } root = root->next; } else if(cur==root->right) { root = root->next; } else { // cur is the child of the previous node of root if(!root->left && !root->right) { root = root->next; continue; } cur->next = root->left ? root->left : root->right; cur = cur->next; } } connect(leftMost); } };

递归不是constant space的，也可以写成迭代解：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

class Solution { public: void connect(TreeLinkNode *root) { TreeLinkNode *leftMost = root; while(leftMost) { root = leftMost; while(root && !root->left && !root->right) root = root->next; if(!root) return; leftMost = root->left ? root->left : root->right; TreeLinkNode *cur = leftMost; while(root) { if(cur==root->left) { if(root->right) { cur->next = root->right; cur = cur->next; } root = root->next; } else if(cur==root->right) { root = root->next; } else { // cur is the child of the previous node of root if(!root->left && !root->right) { root = root->next; continue; } cur->next = root->left ? root->left : root->right; cur = cur->next; } } } } };