LeetCode: Populating Next Right Pointers in Each Node

2020_07_15_populating-next-right-pointers-in-each-node.org_20200715_144225.png

Iteractive algorithm with queue

This is a simple version of level-order traverse.

 class Solution {
public:
    Node* connect(Node* root) {
        queue<Node*> Q;
        Node* cur;
        if(root) Q.push(root);
        while(!Q.empty()) {
            int sz = Q.size();
            Node* pre = NULL;
            for(int i=0; i<sz; i++) {
                cur = Q.front(); Q.pop();
                if(cur->left) Q.push(cur->left);
                if(cur->right) Q.push(cur->right);
                if(pre) pre->next = cur;
                pre = cur;
            }
        }
        return root;
    }
};
Last Updated on

Leave a Reply

Your email address will not be published. Required fields are marked *