116. 填充每个节点的下一个右侧节点指针（三种实现及讲解）

题目：

给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

struct Node { int val; Node *left; Node *right; Node *next; }

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

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

解法1：从上至下打印二叉树的思路，一层层完成连接

class Solution { public: Node* connect(Node* root) { if (NULL == root) return NULL; queue<Node*> que; que.push(root); Node* node; while (!que.empty()){ int len = que.size(); while (len--) { //每层的节点 node = que.front(); que.pop(); if (0 != len) //区别其他节点和右边最后一个节点 node->next = que.front(); else node->next = NULL; if (node->left) que.push(node->left); if (node->right) que.push(node->right); } } return root; } };

 解法2：使用已完成的next指针

       当前层完成next后，通过这层的链表，去完成其下一层的连接。

注：因为当前层已完成连接，所以下一层左子树右子节点和右子树左子节点，可以通过当前层的next指针找到其右子树根节点。因为next指针默认都为空，所以完成非空节点之间的next连接即可。

class Solution { public: Node* connect(Node* root) { if (NULL == root) return NULL; Node *node = root, *curNode; while (node->left) { //当前层最左边节点还有下一层左子节点 curNode = node; //当前层最左边节点 while (curNode) { curNode->left->next = curNode->right; //连接下一层的左右节点 if (curNode->next) curNode->right->next = curNode->next->left;//利用当前层已完成的next指针，找到下一层右节点左子节点 curNode = curNode->next; //连接当前层下一节点的左右子节点next指针 } node = node->left; //在下一层完成连接的情况下，处理下下层 } return root; } };

解法3：原子操作递归实现

       将所有的连接操作抽象提取，即：对当前层某节点next连接后，递归函数去分别完成其左子节点和右子节点next连接。说起来有点绕，来个图看一下(手画有点丑，大道理直白就行TT)：

          

       如上左图，整个树的操作可以看做完成当前节点的next连接(实线指针)，然后带动其左右子节点的next连接(虚线指针，即将完成)，以此往复，如上右图，完成整个树的next连接。

class Solution { private: void connectLeftRight(Node *left, Node *right) { if (left) { left->next = right; connectLeftRight(left->left, left->right); //连接节点左右子节点 connectLeftRight(left->right, right ? right->left : NULL);//连接节点右子节点和右节点左子节点的连接 } } public: Node* connect(Node* root) { if (NULL == root) return NULL; //connectLeftRight(root->left, root->right); connectLeftRight(root, NULL); //从根节点开始 return root; } };

       如果理解了本解法思路，就理解了为什么主函数里为啥是connectLeftRight(root, NULL); 而不能是connectLeftRight(root->left, root->right);了。如果写connectLeftRight(root->left, root->right);，那么从第二层的左子节点开始连接next，带动的也只是以这个节点向下形成三角形的底边两个节点，然后以这两个节点为三角形顶点，向下带动三角形底边节点。循环往复，相当于把整个树每层最右边的节点“削掉”了。

      所以隐含关键的一点还是以根节点为第一个“三角形”的顶点，从而带动所有子节点的连接。

      反观解法2和解法3，解法2就是解法3的非递归实现，也是从root节点开始处理。解法3的实现更加“原子化”。