用层次遍历很好做的,但是题目要求是常数级别的空间复杂度,因此需要转换思路。
我们发现:
- 如果设当前层为i,且当前层所有节点的next指针都已经填充,则从第i层的最左边节点出发,可以遍历当前层;
- 设当前节点为第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; } } };