题目


 

题解

该题二叉树结构如下：

// 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. 递归法

//这道题是#102层次遍历的应用
class Solution {//三种方法。1、递归法
//严格来说这个递归法与#102的不一样，应该是用的先序遍历的递归思想
public:
    Node* connect(Node* root) {
        if(!root) return nullptr;//特殊情况
        if(root->left) root->left->next = root->right;
        //因为是完全二叉树，若左子节点存在，则其next指向右子节点
        if(root->right) root->right->next = root->next? root->next->left : nullptr;
        //若右子节点存在，则若该节点next有值，则指向next的左子节点，否则指向空
        connect(root->left);
        connect(root->right);//按先序遍历顺序递归左右子树
        return root;
    }
};

2. 队列递归法

//这道题是#102层次遍历的应用
class Solution {//三种方法。2、队列迭代法
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;
    }
};

3. 双指针法

//这道题是#102层次遍历的应用
class Solution {//三种方法。3、双指针法
public:
    Node* connect(Node* root) {
        if(!root) return nullptr;//特殊情况
        Node *start = root, *cur = nullptr;//初始化两个指针
        while(start->left){//当start指针的左子树存在，继续迭代
            cur = start;//设置cur指向start
            while(cur){//当cur存在，说明这一层还没迭代完，继续迭代
                cur->left->next = cur->right;//cur的左子树指向右子树
                if(cur->next) cur->right->next = cur->next->left;//若cur->next存在,则其右子树指向cur->next的左子树
                cur = cur->next;//cur指向下个节点
            }
            start = start->left;//start指向start的左子树
        }
        return root;
    }
};