LeetCode: Populating Next Right Pointers in Each Node

With algorithm of level traverse of a binary tree

file:img/2020_07_15_populating-next-right-pointers-in-each-node.org_20200715_144225.png

Iterative 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;
    }
};

Join my Email List for more insights, It's Free!😋

← LeetCode: Add Strings LeetCode: Clone Binary Tree With... →