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


  • 2

    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:
            void connect(TreeLinkNode *root) {
                if(!root)   return;
                
                queue<TreeLinkNode*> q;
                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 ***/
                    TreeLinkNode* dummy=new TreeLinkNode(-1);
                    dummy->next=q.front();
                    TreeLinkNode* cur=q.front(), *prev=dummy;
                    /*** 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;
                }
            }
        };

  • 1

    Here is a recursion version .

    Much shorter than the non-recursion version.

    class Solution {
    public:
        void connect(TreeLinkNode *root) {
            if(!root || !root->left)  return;
            help(root->left, root->right);
        }
        
        void help(TreeLinkNode* a, TreeLinkNode* b){
            a->next=b;
            if(a->left){
                help(a->left, a->right);
                help(a->right, b->left);
                help(b->left, b->right);
            }
        }
    };

  • 0
    F
    class Solution {
    public:
        void connect(TreeLinkNode *root) {
            if(!root)  return;
            deque<TreeLinkNode*> dq;
            dq.push_back(root);
            while (!dq.empty()) {
                int count = dq.size();
                while (count > 0) {
                    TreeLinkNode* cur = dq.front();
                    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);
                }
            }
        }
    };

Log in to reply
 

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