跟昨天的那个题Populating Next Right Pointers in Each Node,意思差不多。只不过把完全二叉树换成了任意二叉树。
所以需要考虑没有孩子节点,只有左孩子节点,只有右孩子节点的情况。代码如下:
class Solution { public: void connect(TreeLinkNode *root) { for(;root!=NULL;) { TreeLinkNode *tmpP=root; if(root->left!=NULL) { root=root->left; }else { root=root->right; } if(root==NULL) { root=tmpP->next; continue; } createConnect(root,tmpP); } } void createConnect(TreeLinkNode *dest,TreeLinkNode *parent) { if(dest==NULL) return; TreeLinkNode *tmpP,*tmpD; for(tmpP=parent,tmpD=dest;tmpP!=NULL;tmpP=tmpP->next) { if(tmpP->left!=NULL) { tmpD->next=tmpP->left; tmpD=tmpD->next; } if(tmpP->right!=NULL) { tmpD->next=tmpP->right; tmpD=tmpD->next; } if(tmpD==tmpD->next) tmpD->next=NULL; } } };