LeeCode_Populating Next Right Pointers in Each Node II

3141 단어 LeetCode
Follow up for problem "Populating Next Right Pointers in Each Node".
What if the given tree could be any binary tree? Would your previous solution still work?
Note:
You may only use constant extra space.
For example, Given the following binary tree,
         1
       /  \
      2    3
     / \    \
    4   5    7

After calling your function, the tree should look like:
         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \    \
    4-> 5 -> 7 -> NULL

제목이 위에서 보듯이 이 문제는 I에서 추궁한 결과 첫 번째 문제가 너무 빨리 제출되어 이 문제의 대의를 초래했다. 원래는 귀속적인 방법으로 해답을 구하려고 했지만 해답의 확장 방향이 명확하지 않아 잡담을 하지 않고 바로 그림을 그렸다.
코드는 다음과 같습니다.
 class Solution {
  public:
      void connect(TreeLinkNode *root) {
          TreeLinkNode *pLeftMost=root;
          while (pLeftMost!=NULL){
              TreeLinkNode *ptemp=pLeftMost;
              while (ptemp!=NULL){
                    connectToNext(ptemp);
                    ptemp=ptemp->next;
              }
              pLeftMost=  findLeftMost(pLeftMost);
          } 
          pLeftMost = root;

          while (pLeftMost!=NULL){
              TreeLinkNode *tep=pLeftMost;
              while (tep!=NULL)
              {
                  cout<<tep->val<<" ";
                  tep=tep->next;
              }
              cout<<"# ";
              pLeftMost=  findLeftMost(pLeftMost);
          } 

      }
      TreeLinkNode *findLeftMost(TreeLinkNode *preLeftMost){
          while (preLeftMost!=NULL){
              if(preLeftMost->left!=NULL)
              {
                  return preLeftMost->left;
              }
              if (preLeftMost->right!=NULL)
              {
                   return preLeftMost->right;
              }
              preLeftMost=preLeftMost->next;
          }
          return NULL;
      }
      void connectToNext(TreeLinkNode *root){
          if (root==NULL)
          {
              return;
          }

          TreeLinkNode *pSet=root->left;
          TreeLinkNode *pSetNext=NULL;

          //  
          if (pSet!=NULL){
              // , next 
              // next 
              if(root->right!=NULL){
                  pSet->next=root->right;
                  pSet=root->right;
              }
          }
          else{
              // , next 
              pSet=root->right;
          }

          // 
          if (pSet==NULL)
          {
              /*connectToNext(root->next);*/
              return;
          }

          //find pSet's next 
          TreeLinkNode *ptemp=root->next;
          while (ptemp!=NULL){
              if (ptemp->left!=NULL){
                  pSetNext=ptemp->left;
                  break;
              }
              if (ptemp->right!=NULL){
                  pSetNext=ptemp->right;
                  break;
              }
              ptemp=ptemp->next;
          }
          pSet->next=pSetNext;
        /*  connectToNext(root->next);*/
      }
  };

좋은 웹페이지 즐겨찾기