LeetCode（117）：填充同一层的兄弟节点 II

Medium！

题目描述：

给定一个二叉树

struct TreeLinkNode {
  TreeLinkNode *left;
  TreeLinkNode *right;
  TreeLinkNode *next;
}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

说明:

你只能使用额外常数空间。
使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。

示例:

给定二叉树，

调用你的函数后，该二叉树变为：

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

解题思路：

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

C++解法一：

 1 // Recursion, more than constant space
 2 class Solution {
 3 public:
 4     void connect(TreeLinkNode *root) {
 5         if (!root) return;
 6         TreeLinkNode *p = root->next;
 7         while (p) {
 8             if (p->left) {
 9                 p = p->left;
10                 break;
11             }
12             if (p->right) {
13                 p = p->right;
14                 break;
15             }
16             p = p->next;
17         }
18         if (root->right) root->right->next = p; 
19         if (root->left) root->left->next = root->right ? root->right : p; 
20         connect(root->right);
21         connect(root->left);
22     }
23 };

对于非递归的方法，惊喜的发现之前的方法直接就能用，完全不需要做任何修改，算法思路可参见博客Populating Next Right Pointers in Each Node 每个节点的右向指针http://www.cnblogs.com/grandyang/p/4288151.html

C++解法二：

 1 // Non-recursion, more than constant space
 2 class Solution {
 3 public:
 4     void connect(TreeLinkNode *root) {
 5         if (!root) return;
 6         queue<TreeLinkNode*> q;
 7         q.push(root);
 8         while (!q.empty()) {
 9             int len = q.size();
10             for (int i = 0; i < len; ++i) {
11                 TreeLinkNode *t = q.front(); q.pop();
12                 if (i < len - 1) t->next = q.front();
13                 if (t->left) q.push(t->left);
14                 if (t->right) q.push(t->right);
15             }
16         }
17     }
18 };

虽然以上的两种方法都能通过OJ，但其实它们都不符合题目的要求，题目说只能使用constant space，可是OJ却没有写专门检测space使用情况的test，那么下面贴上constant space的解法，这个解法也是用的层序遍历，只不过没有使用queue了，我们建立一个dummy结点来指向每层的首结点的前一个结点，然后指针t用来遍历这一层，我们实际上是遍历一层，然后连下一层的next，首先从根结点开始，如果左子结点存在，那么t的next连上左子结点，然后t指向其next指针；如果root的右子结点存在，那么t的next连上右子结点，然后t指向其next指针。此时root的左右子结点都连上了，此时root向右平移一位，指向其next指针，如果此时root不存在了，说明当前层已经遍历完了，我们重置t为dummy结点，root此时为dummy->next，即下一层的首结点，然后dummy的next指针清空。

C++解法三：

 1 // Non-recursion, constant space
 2 class Solution {
 3 public:
 4     void connect(TreeLinkNode *root) {
 5         TreeLinkNode *dummy = new TreeLinkNode(0), *t = dummy;
 6         while (root) {
 7             if (root->left) {
 8                 t->next = root->left;
 9                 t = t->next;
10             }
11             if (root->right) {
12                 t->next = root->right;
13                 t = t->next;
14             }
15             root = root->next;
16             if (!root) {
17                 t = dummy;
18                 root = dummy->next;
19                 dummy->next = NULL;
20             }
21         }
22     }
23 };