Leetcode 116. Populating Next Ri

文章作者：Tyan
博客：noahsnail.com  |  CSDN  |  简书

1. Description

Populating Next Right Pointers in Each Node

2. Solution

• Version 1

/**
 * 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*> q1;
        queue<TreeLinkNode*> q2;
        q1.push(root);
        TreeLinkNode* pre = nullptr;
        TreeLinkNode* current = nullptr;
        while(!q1.empty()) {
            current = q1.front();
            q1.pop();
            if(current->left && current->right) {
                q2.push(current->left);
                q2.push(current->right);
            }
            if(pre) {
                pre->next = current;
            }
            pre = current;
            if(q1.empty()) {
                pre = nullptr;
                q1 = q2;
                q2 = {};
            }
        }
    }
};

• Version 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);
        connect(q);
    }

private:
    void connect(queue<TreeLinkNode*>& q) {
        TreeLinkNode* pre = nullptr;
        TreeLinkNode* current = nullptr;
        queue<TreeLinkNode*> q2;
        while(!q.empty()) {
            current = q.front();
            q.pop();
            if(current->left && current->right) {
                q2.push(current->left);
                q2.push(current->right);
            }
            if(pre) {
                pre->next = current;
            }
            pre = current;
        }
        if(!q2.empty()) {
            connect(q2);
        }
    }
};

• Version 3

/**
 * 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;
        }
        while(root) {
            TreeLinkNode* current = root;
            while(current && current->left) {
                current->left->next = current->right;
                if(current->next) {
                    current->right->next = current->next->left;
                }
                current = current->next;
            }
            root = root->left;
        }
    }
};

Reference

1. https://leetcode.com/problems/populating-next-right-pointers-in-each-node/description/