C++实现LeetCode(117.每个节点的右向指针之二)

[LeetCode] 117. Populating Next Right Pointers in Each Node II 每个节点的右向指针之二

Given a binary tree

struct Node {
int val;
Node *left;
Node *right;
Node *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.

Follow up:

• You may only use constant extra space.
• Recursive approach is fine, you may assume implicit stack space does not count as extra space for this problem.

Example 1:

Input: root = [1,2,3,4,5,null,7]
Output: [1,#,2,3,#,4,5,7,#]
Explanation: Given the above binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level.

Constraints:

• The number of nodes in the given tree is less than 6000.
• -100 <= node.val <= 100

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

解法一：

class Solution {
public:
    Node* connect(Node* root) {
        if (!root) return NULL;
        Node *p = root->next;
        while (p) {
            if (p->left) {
                p = p->left;
                break;
            }
            if (p->right) {
                p = p->right;
                break;
            }
            p = p->next;
        }
        if (root->right) root->right->next = p; 
        if (root->left) root->left->next = root->right ? root->right : p; 
        connect(root->right);
        connect(root->left);
        return root;
    }
};

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

解法二：

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

虽然以上的两种方法都能通过 OJ，但其实它们都不符合题目的要求，题目说只能使用 constant space，可是 OJ 却没有写专门检测 space 使用情况的 test，那么下面贴上 constant space 的解法，这个解法也是用的层序遍历，只不过没有使用 queue 了，我们建立一个 dummy 结点来指向每层的首结点的前一个结点，然后指针 cur 用来遍历这一层，这里实际上是遍历一层，然后连下一层的 next，首先从根结点开始，如果左子结点存在，那么 cur 的 next 连上左子结点，然后 cur 指向其 next 指针；如果 root 的右子结点存在，那么 cur 的 next 连上右子结点，然后 cur 指向其 next 指针。此时 root 的左右子结点都连上了，此时 root 向右平移一位，指向其 next 指针，如果此时 root 不存在了，说明当前层已经遍历完了，重置 cur 为 dummy 结点，root 此时为 dummy->next，即下一层的首结点，然后 dummy 的 next 指针清空，或者也可以将 cur 的 next 指针清空，因为前面已经将 cur 赋值为 dummy 了。那么现在想一想，为什么要清空？因为用 dummy 的目的就是要指到下一行的首结点的位置即 dummy->next，而一旦将 root 赋值为 dummy->next 了之后，这个 dummy 的使命就已经完成了，必须要断开，如果不断开的话，那么假设现在 root 是叶结点了，那么 while 循环还会执行，不会进入前两个 if，然后 root 右移赋空之后，会进入最后一个 if，之前没有断开 dummy->next 的话，那么 root 又指向之前的叶结点了，死循环诞生了，跪了。所以一定要记得清空哦。

这里再来说下 dummy 结点是怎样指向每层的首结点的前一个结点的，过程是这样的，dummy 是创建出来的一个新的结点，其目的是为了指向 root 结点的下一层的首结点的前一个，具体是这么做到的呢，主要是靠 cur 指针，首先 cur 指向 dummy，然后 cur 再连上 root 下一层的首结点，这样 dummy 也就连上了。然后当 root 层遍历完了之后，root 需要往下移动一层，这样 dummy 结点之后连接的位置就正好赋值给 root，然后 cur 再指向 dummy，dummy 之后断开，这样又回到了初始状态，以此往复就可以都连上了，代码如下：

解法三： 

class Solution {
public:
    Node* connect(Node* root) {
        Node *dummy = new Node(-1), *cur = dummy, *head = root;
        while (root) {
            if (root->left) {
                cur->next = root->left;
                cur = cur->next;
            }
            if (root->right) {
                cur->next = root->right;
                cur = cur->next;
            }
            root = root->next;
            if (!root) {
                cur = dummy;
                root = dummy->next;
                dummy->next = NULL;
            }
        }
        return head;
    }
};

类似题目：

Populating Next Right Pointers in Each Node

参考资料：

https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/

https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/discuss/37813/java-solution-with-constant-space

https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/discuss/37828/o1-space-on-complexity-iterative-solution