(검지 Offer) 면접 문제 27: 두 갈래 검색 트리와 양방향 체인 테이블

제목:

두 갈래 검색 트리를 입력하여 이 두 갈래 검색 트리를 정렬된 양방향 체인 테이블로 변환합니다.새 결점은 만들 수 없으며 트리의 결점 포인터 방향만 조정해야 합니다.
두 갈래 나무의 정의는 다음과 같다.

struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
};

생각:

두 갈래 나무에서 매 결점마다 두 개의 지향자 결점을 가리키는 바늘이 있고 양방향 체인 테이블에서 매 결점에도 두 개의 바늘이 있는데 그들은 각각 앞의 결점과 뒤의 결점을 가리킨다.두 가지 데이터 구조는 보기에 매우 비슷하다. 어떤 방식으로 두 갈래 검색 트리를 정렬할 수 있는 양방향 체인 테이블이다.
두 갈래 검색 트리에서 뿌리 결점을 두루 훑어볼 때 두 갈래 트리를 세 부분으로 본다. 뿌리 결점, 왼쪽 나무와 오른쪽 나무는 정렬 체인표의 정의에 따라 뿌리 결점의 왼쪽 바늘은 왼쪽 나무 중 가장 큰 결점, 즉 가장 오른쪽 결점을 가리켜야 한다.뿌리 결점의 오른쪽 바늘은 오른쪽 트리에서 가장 작은 결점, 즉 가장 왼쪽의 결점을 가리켜야 한다.
왼쪽 트리, 오른쪽 트리를 모두 정렬된 양방향 정렬 체인표(귀속)로 변환한 후 뿌리 결점과 연결하면 두 갈래 검색 트리 전체가 정렬된 양방향 체인표로 변환된다.
따라서 귀속 함수를 설계할 때 체인 테이블의 헤더 바늘과 꼬리 바늘을 되돌려주고 현재 결점의 좌우 바늘의 방향을 바꿔야 한다.(코드 참조)

코드:

#include <iostream>

using namespace std;

struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
};

TreeNode* ConvertNodes(TreeNode* pRoot,TreeNode** pTail);

TreeNode* Convert(TreeNode* pRoot){
    TreeNode* pTail=NULL;
    return ConvertNodes(pRoot,&pTail);
}

TreeNode* ConvertNodes(TreeNode* pRoot,TreeNode** pTail){
    if(pRoot==NULL)
        return NULL;
    if(pRoot->left==NULL && pRoot->right==NULL){
        *pTail=pRoot;
        return pRoot;
    }
    TreeNode* leftHead=pRoot;
    if(pRoot->left!=NULL){
        leftHead=ConvertNodes(pRoot->left,pTail);
        pRoot->left=*pTail;
        if(*pTail!=NULL)
            (*pTail)->right=pRoot;
        *pTail=pRoot;
    }

    if(pRoot->right!=NULL){
        TreeNode* rightHead=ConvertNodes(pRoot->right,pTail);
        pRoot->right=rightHead;
        if(rightHead!=NULL)
            rightHead->left=pRoot;
    }
    return leftHead;
}

온라인 테스트 OJ:

http://www.nowcoder.com/books/coding-interviews/947f6eb80d944a84850b0538bf0ec3a5?rp=2
AC 코드:

class Solution {
public:
    TreeNode* Convert(TreeNode* pRootOfTree)
    {
        TreeNode* pTail=NULL;
        return ConvertNodes(pRootOfTree,&pTail);
    }

    TreeNode* ConvertNodes(TreeNode* pRoot,TreeNode** pTail){
        if(pRoot==NULL)
            return NULL;
        if(pRoot->left==NULL && pRoot->right==NULL){
            *pTail=pRoot;
            return pRoot;
        }

        TreeNode* leftHead=pRoot;
        if(pRoot->left!=NULL){
            leftHead=ConvertNodes(pRoot->left,pTail);
            pRoot->left=*pTail;
            if(*pTail!=NULL)
                (*pTail)->right=pRoot;
            *pTail=pRoot;
        }

        if(pRoot->right!=NULL){
            TreeNode* rightHead=ConvertNodes(pRoot->right,pTail);
            pRoot->right=rightHead;
            if(rightHead!=NULL)
                rightHead->left=pRoot;
        }
        return leftHead;
    }

};