Leetcode 117. Populating Next Ri

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

1. Description

Populating Next Right Pointers in Each Node II

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

• 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) {
                q2.push(current->left);
            }
            if(current->right) {    
                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;
        }
        TreeLinkNode* parent = root;
        TreeLinkNode* head = new TreeLinkNode(0);
        while(root) {
            parent = root;
            TreeLinkNode* current = head;
            while(parent) {
                if(parent->left && parent->right) {
                    current->next = parent->left;
                    current->next->next = parent->right;
                    current = parent->right;
                }
                else if(parent->left) {
                    current->next = parent->left;
                    current = parent->left;
                }
                else if(parent->right){
                    current->next = parent->right;
                    current = parent->right;
                }
                parent = parent->next;
            }
            current->next = nullptr;
            root = head->next;
        }
        delete head;
    }
};

Reference

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