116. 填充每个节点的下一个右侧节点指针——记录(C++)

class Solution {
public:
    queue<Node*>q;
    Node* connect(Node* root) {
        if(!root) return root;
        q.push(root);
        int sz;
        while(!q.empty())
        {
            sz=q.size();
            Node* n=q.front(); 
              q.pop();
             while(sz>0)
        {
            if(n->left)
            {
            q.push(n->left);
            q.push(n->right);
            }
          if (sz!=1)
            {
                n->next=q.front();  
                q.pop();  
                n=n->next;              
            }
            --sz;
        }
        }
       return  root;
    }
};

116. 填充每个节点的下一个右侧节点指针——记录(C++)

半个小时。

参考了广度优先遍历。

加油。

class Solution {
public:
    Node* connect(Node* root) {
        if (root == nullptr) {
            return root;
        }
        
        // 从根节点开始
        Node* leftmost = root;
        
        while (leftmost->left != nullptr) {
            
            // 遍历这一层节点组织成的链表,为下一层的节点更新 next 指针
            Node* head = leftmost;
            
            while (head != nullptr) {
                
                // CONNECTION 1
                head->left->next = head->right;
                
                // CONNECTION 2
                if (head->next != nullptr) {
                    head->right->next = head->next->left;
                }
                
                // 指针向后移动
                head = head->next;
            }
            
            // 去下一层的最左的节点
            leftmost = leftmost->left;
        }
        
        return root;
    }
};

 这个答案好。

上一篇:CF E. Till I Collapse 整体二分+根号分治


下一篇:[ AGC002 F ] Leftmost Ball