Coder's Cat

LeetCode: Populating Next Right Pointers in Each Node

2020-07-15

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

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