검지offer 시리즈-26.두 갈래 검색 트리와 양방향 체인 시계??

1763 단어
Q: 두 갈래 검색 트리를 입력하여 이 두 갈래 검색 트리를 정렬된 양방향 체인 테이블로 변환합니다.새 결점은 만들 수 없으며 트리의 결점 포인터 방향만 조정해야 합니다.T: 한 창고를 이용하여 두 갈래 나무의 중서 역행을 실현한다. 문제에서 이것은 두 갈래 나무라고 한다. 그러면 두 갈래 나무의 중서 역행은 순서가 있다. 그러면 이때 중서 역행만 할 때 이 노드를 찾을 때 이 노드를 먼저 저장하고 다음 노드를 역행할 때 이전에 저장된 노드의 right역을 다음 결점으로 가리킨다.다음 결점의 왼쪽 영역은 이전 결점을 가리킨다.이렇게 되면 정렬된 양방향 체인 시계가 형성된다.그리고 이전에 저장된 바늘을 현재 이 결점을 가리킨다.
// 
private:
    TreeNode* pLast = nullptr;
public:
    TreeNode* Convert(TreeNode* pRootOfTree)
    {
        if(!pRootOfTree)
            return nullptr;
        TreeNode* head = Convert(pRootOfTree->left);
        if(!head)
            head = pRootOfTree;
        pRootOfTree->left = pLast;
        if(pLast)
           pLast->right = pRootOfTree;
        pLast = pRootOfTree;
        Convert(pRootOfTree->right);
        return head;
    }

// 
public:
    TreeNode* Convert(TreeNode* pRootOfTree)
    {
        TreeNode *head = NULL, *pre = NULL;//head  ,pre 
        stack s;
        while (pRootOfTree || !s.empty())
        {
            while (pRootOfTree)
            {
                s.push(pRootOfTree);
                pRootOfTree = pRootOfTree->left;
            }
            if (!s.empty())
            {
                pRootOfTree = s.top();
                s.pop();
                if (pre != NULL)
                {
                    pre->right = pRootOfTree;
                    pRootOfTree->left = pre;
                }
                else//pre , s , , 
                    {
                    head = pRootOfTree;
                }
                pre = pRootOfTree;
                pRootOfTree = pRootOfTree->right;
            }
        }
        return head;
    }

P.S.는 내가 이 문제를 이해하지 못한 것에 대해 미안하지만...

좋은 웹페이지 즐겨찾기