用层次遍历很好做的,但是题目要求是常数级别的空间复杂度,因此需要转换思路。

我们发现:

  1. 如果设当前层为i,且当前层所有节点的next指针都已经填充,则从第i层的最左边节点出发,可以遍历当前层;
  2. 设当前节点为第i层的第j个节点,那么很容易就能填充节点j在第i+1层的子节点的next指针

于是,产生了如下代码(如果觉得理解不了,可以画画图):

class Solution {
public:
    void connect(TreeLinkNode *root) {
        if (!root) return;
        TreeLinkNode *left = root;
        while(left->left) {
            TreeLinkNode *p = left;
            while (p) {
                p->left->next = p->right;
                if (p->next) p->right->next = p->next->left;
                p = p->next;
            }
            left = left->left;
        }
    }
};