117.md

117. Populating Next Right Pointers in Each Node II

Leetcode link

解题思路——先进先出队列

这道题有两种思路，我们先说第一种队列的思路

首先我们需要一个先进先出的队列，然后我们按照题目要求的顺序从上到下从左到右一次把目标元素填入队列中

值得注意的是每一层的最后一个元素后面记得多填一个 NULL ；然后对于节点空的位置也需要填入 NULL

C++

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

解题思路——递归

另一种思路是使用递归思想配合一个数组

数组的作用在于记录当前的层从左到右还没有记录 next 的第一个节点

Javascript

var connect = function(root) {
    let levelPtr = [];
    
    var addNext = (node, level) => {
        if(!node) {
            return;
        }
      // 因为每一层都是从左到右访问，所以每一层只需要记录最左边还没有记录 next 指针的元素就好
        if(levelPtr[level]) {
            levelPtr[level].next = node;
        }
        levelPtr[level] = node;
        
        addNext(node.left, level+1);
        addNext(node.right, level+1);
    }
    
    addNext(root, 0);
    return root;
};