LeetCode116:填充同一层的兄弟节点

题目说明

给定一个二叉树

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

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

说明:
你只能使用额外常数空间。
使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
你可以假设它是一个完美二叉树（即所有叶子节点都在同一层，每个父节点都有两个子节点）。
示例:
给定完美二叉树，

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

题目分析

最简单的方法其实就是递归，代码少而且也符合要求。由于是完美的二叉树，因此只要将左节点指向右节点，右节点指向其next的左孩子就可以，因为已经在上层确定了两个父节点的关系。代码2用的方法是非递归的方法，由于需要进行层次遍历，毫无疑问使用队列的数据结构。需要注意的是NULL节点的插入位置，可以用来作为分层的表示。
如果要使用非递归方法，且使用额外的常数空间，根据网上的相关资料，使用的是两个指针来进行便利，一个指针指向每层的第一个，另一个来遍历该层，看代码3还是比较容易理解的。

代码1

class Solution {
public:
    void connect(TreeLinkNode *root) {
        if(!root) return;
        if(root->left) root->left->next = root->right;
        //通过三元运算符也把根节点的指向确定了
        if(root->right) root->right->next = root->next ? root->next->left : NULL;
        connect(root->left);
        connect(root->right);
    }
};

代码2

/**
 * 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;
        queue<TreeLinkNode*> q;
        q.push(root);
        q.push(NULL);
        while(1) {
            TreeLinkNode* cur = q.front();
            q.pop();
            //当队列头不为NULL
            if(cur) {
                //将弹出的元素指向此时的队列头
                cur->next = q.front();
                if(cur->left) q.push(cur->left);
                if(cur->right) q.push(cur->right);
            }
            //当队列头为NULL,这里是关键
            //意味着这一层已经遍历完，这一层的子节点也都加入队列，此时需要在队列尾插入下一层的NULL
            else {
                //当遍历到队列最尾端，就是没有元素了。
                //插入NULL之后，就是val为NULL,所以不会在root之后的NULL退出
                if( q.front()==NULL || q.size() == 0) return;
                q.push(NULL);
            }
        }
    }
};

代码3

class Solution {
public:
    void connect(TreeLinkNode *root) {
        if (!root) return;
        TreeLinkNode *start = root, *cur = NULL; 
        while( start->left ) {
            cur = start;
            while( cur ) {
                cur->left->next = cur->right;
                if( cur->next ) {
                    cur->right->next = cur->next->left;
                }
                cur = cur->next;
            }
            start = start->left;
        }
    }
};