두 갈래 나무 관련 필기시험 문제 (3)

1. 지그재그 순서로 두 갈래 나무 인쇄
제목: 함수를 실현하여 지그재그 순서에 따라 두 갈래 나무를 인쇄하십시오. 즉, 첫 번째 줄은 왼쪽에서 오른쪽으로, 두 번째 줄은 오른쪽에서 왼쪽으로, 세 번째 줄은 왼쪽에서 오른쪽으로 인쇄합니다.
분석: 두 개의 창고를 사용하여 어떤 층의 결점을 인쇄할 때 다음 층의 자결점을 해당하는 창고에 저장할 수 있다.현재 레이어가 홀수 레이어인 경우 왼쪽 서브노드를 저장한 다음 첫 번째 스택에 오른쪽 서브노드를 저장하고, 짝수 레이어인 경우 왼쪽 서브노드를 두 번째 스택에 저장합니다.
구현 코드 1:

    vector<vector<int> > Print(TreeNode* pRoot) {
        vector<vector<int> > result;
        stack<TreeNode *> stack1,stack2;
        if(pRoot!=NULL)
            stack1.push(pRoot);
        TreeNode *node = NULL;
        while(!stack1.empty() || !stack2.empty()){
            vector<int> data;
            if(!stack1.empty()){
                while(!stack1.empty()){
                    node = stack1.top();
                    stack1.pop();
                    data.push_back(node->val);
                    if(node->left!=NULL)
                        stack2.push(node->left);
                    if(node->right!=NULL)
                        stack2.push(node->right);
                }
                result.push_back(data);
            }
            else if(!stack2.empty()){
                while(!stack2.empty()){
                    node = stack2.top();
                    stack2.pop();
                    data.push_back(node->val);
                    if(node->right!=NULL)
                        stack1.push(node->right);
                    if(node->left!=NULL)
                        stack1.push(node->left);
                }
                result.push_back(data);
            }
        }
        return result;
    }

구현 코드 2:

    vector<vector<int> > Print(TreeNode* pRoot) {
        vector<vector<int> > result;      
        if(pRoot == NULL)
            return result;
          
        bool flag = true;
          
        queue<TreeNode *> q;        
        q.push(pRoot);         
        while(!q.empty())
        {
            int size = q.size();
            vector<int> num;
            while(size --)
            {
                TreeNode *cur = q.front();
                q.pop();
                num.push_back(cur->val);
                if(cur->left != NULL)
                {
                    q.push(cur->left);
                } 
                if(cur->right != NULL)
                {
                    q.push(cur->right);
                } 
            }
            if(!flag) 
            {
                reverse(num.begin(), num.end());
            }
            result.push_back(num);
            flag = !flag;
        }
        return result;
    }

이..두 갈래 나무를 여러 줄로 인쇄하다
제목: 위에서 아래로 두 갈래 트리를 인쇄하고 같은 층의 결점은 왼쪽에서 오른쪽으로 순서대로 인쇄하며 한 층마다 한 줄을 인쇄한다.
분석: 겹겹이 두 갈래 나무를 훑어보는 것과 비슷하다.
구현 코드:

        vector<vector<int> > Print(TreeNode* pRoot) 
        {
            vector<vector<int> > vec;
             
            if(pRoot == NULL) 
                return vec;
  
            queue<TreeNode*> q;
            q.push(pRoot);
  
            while(!q.empty())
            {
                int lo = 0;
                int hi = q.size();
                vector<int> c;
                while(lo++ < hi)
                {
                    TreeNode *t = q.front();
                    q.pop();
                    c.push_back(t->val);
                    if(t->left) 
                    {
                        q.push(t->left);
                    }                      
                    if(t->right)
                    {
                        q.push(t->right);
                    }                        
                }
                vec.push_back(c);
            }
            return vec;
        }   

3. 서열화 두 갈래 나무
분석: 두 갈래 나무의 순서에 따라 뿌리 노드를 먼저 훑어보고 왼쪽 결점, 뒤 오른쪽 노드를 훑어보고'#'에 이르면 왼쪽 결점이나 오른쪽 노드가 NULL이라는 것을 설명한다. 마찬가지로 반서열화도 마찬가지다.
구현 코드:

    char* Serialize(TreeNode *root) {    
        if(root==NULL)
            return NULL;
        string str;
        Serialize1(root,str);
        return const_cast<char*>(str.c_str());
    }
    TreeNode* Deserialize(char *str) {
        if(str==NULL||*str=='\0')
            return NULL;
        int num=0;
        return Deserialize1(str,num);
    }
    void Serialize1(TreeNode *root,string &str)
    {
        if(root==NULL)
        {
            str+="#,";
            return ;
        }
        char ch[10];
        sprintf(ch,"%d",root->val);
        str+=ch;
        str+=",";
        Serialize1(root->left,str);
        Serialize1(root->right,str);
    }
    TreeNode* Deserialize1(char *str,int &num)
    {
        int val=0;
        if(str[num]=='#')
        {
            num+=2;
            return NULL;
        }
        while(str[num]!=','&&str[num]!='\0')
        {
            val=val*10+str[num]-'0';
            num++;
        }
        num++;
        TreeNode *root=new TreeNode(val);
        root->left=Deserialize1(str,num);
        root->right=Deserialize1(str,num);
        return root;
    }

4. 두 갈래 검색 트리의 K번째 결점
제목: 두 갈래 검색 트리를 정하고 그 중 두 번째로 큰 결점을 찾아보세요.
분석: 중서가 두 갈래 검색 트리를 두루 다니는데 두루 돌아다니는 서열이 점차 증가하기 때문에 중서가 두루 다니면 K의 큰 결점을 찾을 수 있다.
구현 코드:

    TreeNode* KthNode(TreeNode* pRoot, unsigned int& k)
    {
        if(pRoot == NULL || k == 0)
        {
            return NULL;
        }
        TreeNode* ret = NULL;
        if(pRoot->left != NULL)
        {
            ret = KthNode(pRoot->left, k);    
        }
        if(ret == NULL)
        {
            if(k == 1)
            {
                ret = pRoot;
            }
            else
            {
                k--;
            }
        }
        if(ret == NULL && pRoot->right != NULL)
        {
            ret = KthNode(pRoot->right, k);
        }
        return ret;
    }