题目

题解

该题二叉树结构如下：

// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};

1.递归法

//和#116类似
class Solution {//三种方法。1、递归法(#116的升级版)
public:
    Node* connect(Node* root) {
        if(!root) return nullptr;//特殊情况
//主要区别
        Node *p = root->next;//p指向root的next，
        while(p){
            if(p->left){
                p = p->left;
                break;
            }
            if(p->right){
                p = p->right;
                break;
            }
            p = p->next;
        }//这一部分用于找该子节点的next，若父节点的左子树或右子树存在，则next为该子树，否则一直遍历到nullptr
        if(root->right) root->right->next = p;//右子树指向上面找到的节点
        if(root->left) root->left->next = root->right? root->right : p;//若右子树不存在，则指向p，否则指向右子节点
//主要区别
        connect(root->right);
        connect(root->left);//注意这里要先右后左
        return root;
    }
};

2. 队列递归法

//和#116类似
class Solution {//三种方法。2、队列迭代法(和#116完全一样，细节见#116)
public:
    Node* connect(Node* root) {
        if(!root) return nullptr;//特殊情况
        queue<Node*> q;//建立队列
        q.push(root);//将根节点压入队列
        while(!q.empty()){//当队列不为空，继续迭代
            for(int i=q.size(); i>0; i--){//对当前行处理，细节见#102
                auto tmp = q.front();q.pop();
                if(i>1) tmp->next = q.front();//与#102主要区别1，除了最后一个数外其他节点指向队首
                if(tmp->left) q.push(tmp->left);
                if(tmp->right) q.push(tmp->right); //这与#102一样
            }
        }
        return root;
    }
};

上述两种方法时间/空间复杂度为$O(N)$,题目要求可以用常数空间复杂度，下面这个方法使用常数复杂度。

3. 三指针法

class Solution {//三种方法。3、三指针法(#116的升级版)
public:
    Node* connect(Node* root) {
        Node* Dummy = new Node(0,nullptr,nullptr,nullptr);
        //哑节点可以解决没有最左子树的问题
        Node *cur = Dummy, *father = root;
        //两个指针，一个用来遍历子层，一个用来遍历父层
        while(father){//当父层遍历未结束
            if(father->left){
                cur->next = father->left;
                cur = cur->next;
            }//若该父节点左子树存在，则子层cur指向该子树
            if(father->right){
                cur->next = father->right;
                cur = cur->next;
            }//右子树同上
            father = father->next;//遍历下一个父节点
            if(!father){
                cur = Dummy;
                father = cur->next;
                Dummy->next = nullptr;
            }//父层遍历结束，cur返回哑节点，父层指针回到子层最左，哑节点断开
        }
        return root;
    }
};