117.每个节点的右向指针之二 C++实现LeetCode_生活百科

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.

【117.每个节点的右向指针之二 C++实现LeetCode】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 又指向之前的叶结点了，死循环诞生了，跪了。所以一定要记得清空哦。