Populating Next Right Pointers in Each Node的变形:
http://blog.sina.com.cn/s/blog_672f71fc0101ohqp.html
但是貌似自己没有使用常数空间
class Solution { public: void connect(TreeLinkNode *root) { // Note: The Solution object is instantiated only once and is reused by each test case. int height = -1; TreeLinkNode * rootheight = root; while(rootheight != NULL) { height++; rootheight = rootheight->left; } int NumOfNodes = (int)pow(2.0,height+1) - 1; TreeLinkNode ** LinkNodeArray = new TreeLinkNode *[1000000]; int index = 0; LinkNodeArray[index++] = root; int bottom = 0; int top = index; while(true) { if(bottom == top) break; for(int i = bottom;i < top;i++) { if(LinkNodeArray[i] == NULL) continue; if(i == top-1) { LinkNodeArray[i] ->next = NULL; if(LinkNodeArray[i]->left != NULL) LinkNodeArray[index++] = LinkNodeArray[i]->left; if(LinkNodeArray[i]->right != NULL) LinkNodeArray[index++] = LinkNodeArray[i]->right; } else { LinkNodeArray[i] ->next = LinkNodeArray[i+1]; if(LinkNodeArray[i]->left != NULL) LinkNodeArray[index++] = LinkNodeArray[i]->left; if(LinkNodeArray[i]->right != NULL) LinkNodeArray[index++] = LinkNodeArray[i]->right; } } bottom = top; top = index; } } };