My C++ Solution


  • 1
    H
    class Solution {
    public:
        void connect(TreeLinkNode *root) {
            connectRight(root);
        }
        // 因为不是按树的 level 来执行连接
        // 可能会出现上层还未连接,导致下一层没法跨越空白区域
        // 按level 连接需要一个队列,因为题目要求 O(1)空间。
        // 所以只好分两次做了。
        // 第一次连接同个节点的左右子节点。
        // 第二次连接子节点到隔壁节点
    
        /*  发现先遍历右边的话,就可以解决上面的问题 !!! */
        void connectRight(TreeLinkNode* curr)
        {
            if(curr == NULL)
                return;
            // 连接节点左右子节点
            if(curr -> left)
                curr -> left -> next = curr -> right;
            // 连接隔壁子节点
            if(curr -> next)
            {
                TreeLinkNode* avlRight = NULL;
                TreeLinkNode* right = curr -> next;
                // 尽力找到一个右边可以连接的点
                while(right)
                {
                    avlRight = right -> left ? right -> left : right -> right;
                    if(avlRight)
                        break;
                    right = right -> next;
                }
                // 找一个左边可以连接的点
                TreeLinkNode* avlLeft = curr -> right ?  curr -> right : curr -> left;
                if(avlLeft)
                    avlLeft -> next = avlRight;
            }
            connectRight(curr -> right);
            connectRight(curr -> left);
            
        }
    };

  • 0
    L

    my simple C++ solution 40ms

    class Solution {
    public:
        void connect(TreeLinkNode *root) 
        {
           if(!root)return ;
           deque<TreeLinkNode*> cur;
           cur.push_back(root);
           while(!cur.empty())
           {
              deque<TreeLinkNode*> next;
              while(!cur.empty())
              {
                TreeLinkNode *out=cur[0];
                cur.pop_front();
                if(out->left)
                {
                  next.push_back(out->left);
                }
                if(out->right)
                {
                  next.push_back(out->right);
                }
              
                if(!cur.empty())
                 out->next=cur[0];
                else
                 out->next=nullptr;
              }
              cur=std::move(next);
             
           }
           
        }
    };

  • 0
    Z

    What is the space complexity of your algorithm?


  • 0
    L

    the "cur" will contain the nodes of each level in the tree,though less than o(n) space complexity,yeah,it's not in o(1) space complexity


Log in to reply
 

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