Simple recursive and iterative solutions.


  • 0
    C
    //Recursive
    class Solution {
        //connect rhs nodes for LHS subtree with lhs nodes of RHS subtree
        void connectLSTrhsRSTlhs(TreeLinkNode *lhs, TreeLinkNode *rhs) {
            while (lhs && rhs) {
                lhs->next = rhs;
                lhs = lhs->right; 
                rhs = rhs->left;
            }
        }
        
        //set rhs of right sub tree to NULL
        void nullifyRSTrhs(TreeLinkNode* rhs) {
            while (rhs) {
                rhs->next = NULL;
                rhs = rhs->right;
            }
        }
        
    public:
        void connect(TreeLinkNode *root) {
            if (root == NULL) return;
            connect(root->left);
            connect(root->right);
            connectLSTrhsRSTlhs(root->left, root->right);
            nullifyRSTrhs(root->right);
        }
    };
    
    //Iterative
    class Solution {
    public:
        void connect(TreeLinkNode *root) {
            if (root == NULL) return;
            root->next = 0; //clobbering next pointer to store level temporarily
            
            deque<TreeLinkNode*> que;
            que.push_back(root);
            TreeLinkNode *me = NULL;
            
            while (!que.empty()) {
                me = que.front(); que.pop_front();
                if (me->left) {
                    me->left->next = me->next+1;
                    que.push_back(me->left);
                }
                if (me->right) {
                    me->right->next = me->next+1;
                    que.push_back(me->right);
                }
                if (que.empty() || que.front()->next != me->next) {
                    me->next = NULL;
                } else {
                    me->next = que.front();
                }
            }
        }
    };

Log in to reply
 

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