lintcode - 두 갈래 나무를 체인 테이블로 분해

2118 단어 두 갈래 나무
1. 제목
두 갈래 나무를 앞의 순서에 따라 두루 분해하여 하나로 만든다 .가짜 체인 시계란 두 갈래 나무의right 바늘로 체인 시계의next 바늘을 나타내는 것이다.
주의사항
왼쪽 아들을null로 표시하는 것을 잊지 마라. 그렇지 않으면 공간이 넘치거나 시간이 넘칠 수도 있다.
예제
              1
               \
     1          2
    / \          \
   2   5    =>    3
  / \   \          \
 3   4   6          4
                     \
                      5
                       \
                        6

2. 생각
먼저 앞의 순서대로 두 갈래 트리를 저장하는 함수save를 씁니다. 이 함수는 두 갈래 트리를 앞의 순서대로 벡터에 저장합니다.
save 함수를 호출하여 주어진 두 갈래 트리를 벡터에 저장한 다음 벡터 안의 요소를 순서대로 체인표로 전개하여 체인표로 전환하는 과정에서root->left를 공백으로 표시하는 것을 기억하십시오.
3. 코드
/**  * Definition of TreeNode:  * class TreeNode {  * public:  *     int val;  *     TreeNode *left, *right;  *     TreeNode(int val) {  *         this->val = val;  *         this->left = this->right = NULL;  *     }  * }  */class Solution { public:    /**      * @param root: a TreeNode, the root of the binary tree      * @return: nothing      */    vectorv;     void save(TreeNode *root)     {         if(root==NULL)             return;         else{             v.push_back(root->val);             save(root->left);             save(root->right); }//벡터로 앞의 결과를 저장하는 함수 void flatten (TreeNode*root) {//write your code here save (root);//호출 함수 저장에 지정된 트리 Node*r, *temp;temp=root;//수조에 저장된 요소를 체인 테이블 for(int i=1;i         {             r=new TreeNode(v[i]);             temp->left=NULL;             temp->right=r;             temp=r;         }     } };
소감
원래는 원래의 두 갈래 나무를 직접 바꾸어 바늘로 바꾸려고 했는데, 자신을 어지럽히고, ac도 없으니, 짬을 내서 다시 이걸 쓰려고 썼다!코드 저장/* if (root==NULL) return;        if(root->left==NULL)             { flatten(root->right);               return;             }          TreeNode *l=root->left;          TreeNode *r=root->right;          flatten(l);          flatten(r);          root->left=NULL;          root->right=l;          while(l->right!=NULL)           {              l=l->right;              l->right=r;           }
   ——————————————————————
     
   


좋은 웹페이지 즐겨찾기