# [recommend for beginners]consice & clean C++ implementation with detailed explaination

• As far as I am concerned this problem and the next problem "Populating Next Right Pointers in Each Node II " is just the same problem to get the depth of the binary tree without recursive solution.

We just need to deal with the node list level by level

Here first is the non-recursive implementation of the get the depth of
the binary tree

``````int getHeight(TreeNode* root){
if (!root)	return 0;
queue<TreeNode*> q;
q.push(root);
int result = 0;

while (1){
int cur_count = q.size();
if (cur_count == 0)
return result;
result++;
//pop out all the cur level node
while (cur_count > 0){
TreeNode* node = q.front();
q.pop();
if (node->left != NULL)
q.push(node->left);
if (node->right != NULL)
q.push(node->right);
cur_count--;
}
}
}
``````

Here is the solution of the problem

``````class Solution {
public:
if(!root)   return;

q.push(root);
int cur_count=0;
while(!q.empty()){
/*** record the level count of the queue  ***/
cur_count=q.size();
/*** use the dummy head node to make code clean ***/
dummy->next=q.front();
/*** linked all the current level node pointer ***/
while(cur_count >= 1){
if(cur->left)   q.push(cur->left);
if(cur->right)   q.push(cur->right);
q.pop();
prev->next=cur;
prev=cur;
cur=q.front();
cur_count--;
}
/*** set the tail node of the current level ***/
prev->next=NULL;
}
}
};``````

• Here is a recursion version .

Much shorter than the non-recursion version.

``````class Solution {
public:
if(!root || !root->left)  return;
help(root->left, root->right);
}

a->next=b;
if(a->left){
help(a->left, a->right);
help(a->right, b->left);
help(b->left, b->right);
}
}
};``````

• ``````class Solution {
public:
if(!root)  return;
dq.push_back(root);
while (!dq.empty()) {
int count = dq.size();
while (count > 0) {
dq.pop_front();
count--;
if (count > 0)
cur->next = dq.front();
else
cur->next = nullptr;
if (cur->left) dq.push_back(cur->left);
if (cur->right) dq.push_back(cur->right);
}
}
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.