该题需要使用常数级别的空间,所以无法使用vector、queue等辅助空间
/** * Definition for binary tree with next pointer. * struct TreeLinkNode { * int val; * TreeLinkNode *left, *right, *next; * TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {} * }; */ class Solution { public: void connect(TreeLinkNode *root) { if(!root) { return ; } TreeLinkNode *temp = root; while(temp->left) { TreeLinkNode *p = temp; while(p) //相当于循环p的下一层,若有左节点就让它等于p的右节点,如若p 仍有next ,则它的右节点的next便必定是next的左节点 { p->left->next = p->right; if(p->next) p->right->next = p->next->left; p = p->next; } temp = temp->left; } } };