117. Populating Next Right Pointers in Each Node II (Medium)

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

Solution 1: Recursion

这道是之前那道Populating Next Right Pointers in Each Node 每个节点的右向指针的延续，原本的完全二叉树的条件不再满足，但是整体的思路还是很相似，仍然有递归和非递归的解法。我们先来看递归的解法，这里由于子树有可能残缺，故需要平行扫描父节点同层的节点，找到他们的左右子节点。代码如下：

要先recursive on right half!

/**
 * Definition for binary tree with next pointer.
 * struct TreeLinkNode {
 *  int val;
 *  TreeLinkNode *left, *right, *next;
 *  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
 * };
 */
class Solution {
public:
    void connect(TreeLinkNode *root) {
        if (!root) return;
        TreeLinkNode* p = root->next;
        // find next possible sibling
        while (p) {
            if (p->left) { p = p->left; break; }
            if (p->right) { p = p->right; break; }
            p = p->next;
        }
        if (root->left) root->left->next = root->right ? root->right:p;
        if (root->right) root->right->next = p;
        connect(root->right);
        connect(root->left);
    }
};

Solution 2: Iteration

对于非递归的方法，我惊喜的发现之前的方法直接就能用，完全不需要做任何修改，算法思路可参见之前的博客Populating Next Right Pointers in Each Node 每个节点的右向指针，代码如下：

class Solution {
public:
    void connect(TreeLinkNode *root) {
        if (!root) return;
        queue<TreeLinkNode*> q;
        q.push(root);
        while (!q.empty()) {
            int size = q.size();
            for (int i = 0; i < size; ++i) {
                TreeLinkNode* cur = q.front(); q.pop();
                cur->next = (i == size-1) ? NULL:q.front();
                if (cur->left) q.push(cur->left);
                if (cur->right) q.push(cur->right);
            }
        }
    }
};

Solution 3: 26ms

Space Complexity: $$O(1)$$

version 1:
//based on level order traversal

class Solution {
public:
    void connect(TreeLinkNode *root) {
        TreeLinkNode* head = NULL; //head of the next level
        TreeLinkNode* prev = NULL; //the leading node on the next level
        TreeLinkNode* cur = root;  //current node of current level
        while (cur) {
            while (cur) { // iterate on the current level
                // left child
                if (cur->left) {
                    if (prev) prev->next = cur->left;
                    else head = cur->left;
                    prev = cur->left;
                }

                // right child
                if (cur->right) {
                    if (prev) prev->next = cur->right;
                    else head = cur->right;
                    prev = cur->right;
                }
                //move to next node
                cur = cur->next;
            }

            //move to next level
            cur = head;
            head = prev = NULL;
        }
    }
};

version 2:

虽然以上的两种方法都能通过OJ，但其实它们都不符合题目的要求，题目说只能使用constant space，可是OJ却没有写专门检测space使用情况的test，那么下面贴上constant space的解法，这个解法乍看上去蛮复杂，但是仔细分析分析也就那么回事了，首先定义了一个leftMost的变量，用来指向每一层最左边的一个节点，由于左子结点可能缺失，所以这个最左边的节点有可能是上一层某个节点的右子结点，我们每往下推一层时，还要有个指针指向上一层的父节点，因为由于右子节点的可能缺失，所以上一层的父节点必须向右移，直到移到有子节点的父节点为止，然后把next指针连上，然后当前层的指针cur继续向右偏移，直到连完当前层所有的子节点，再向下一层推进，以此类推可以连上所有的next指针，代码如下：

class Solution {
public:
    void connect(TreeLinkNode *root) {
        if (!root) return;
        TreeLinkNode* leftMost = root;
        while (leftMost) {
            // prev level
            TreeLinkNode* p = leftMost;
            while (p && !p->left && !p->right) p = p->next;
            if (!p) return; // current level does not exist
            leftMost = p->left ? p->left : p->right;
            // current level
            TreeLinkNode* cur = leftMost;
            while (p) {
                if (cur == p->left) {
                    if (p->right) {
                        cur->next = p->right;
                        cur = cur->next;
                    }
                    p = p->next;
                } else if (cur == p->right) {
                    p = p->next;
                } else {
                    if (!p->left && !p->right) { p = p->next; continue;}
                    cur->next = p->left ? p->left:p->right;
                    cur = cur->next;
                }
            }
        }
    }
};