my BFS c++ solution


  • 0

    After I solved this problem, I saw it was tagged as DFS. While my first thoughts towards this problem is BFS. I think using BFS is very easy to understand. Here is my code:

    class Solution {
    public:
        void BFS(unordered_map<int,TreeLinkNode*>& v,TreeLinkNode* node){
            int val = 0;
            queue<TreeLinkNode*> myQ;
            myQ.push(node);
            v[val] = node;
            while(!myQ.empty()){
                TreeLinkNode* head = myQ.front();
                myQ.pop();
                if(head != NULL){
                    if(head->left != NULL){
                        v[++val] = head->left;
                        myQ.push(head->left);
                    }
                    if(head->right != NULL){
                         v[++val] = head->right;
                        myQ.push(head->right);
                    }
       
                }
            }
            return;
        }
        void connect(TreeLinkNode *root) {
            if(root == NULL) return;
            unordered_map<int,TreeLinkNode*>myNodes;
            BFS(myNodes, root);
            int len = myNodes.size();
            int nodeNum = 1;
            int i = 0, j = 0;
            for(;i < len;){
                for( int j = 0; j < nodeNum; j++,i++){
                    if(j == nodeNum - 1){
                        myNodes[i]->next = NULL; 
                    }else{
                        myNodes[i]->next = myNodes[i+1]; 
                    }
                }
                nodeNum *= 2;
            }
            return;
            
        }    
    };
    

Log in to reply
 

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