【검지offer】 두 갈래 검색 트리와 양방향 체인 테이블(이차 트리+체인 테이블)
5629 단어 검지offer
제목 설명
두 갈래 검색 트리를 입력하여 이 두 갈래 검색 트리를 정렬된 양방향 체인 테이블로 변환합니다.새 결점은 만들 수 없으며 트리의 결점 포인터 방향만 조정해야 합니다.
생각
두 갈래 나무에는 좌우 두 개의 바늘이 있다.쌍방향 체인표에도 앞뒤 두 개의 바늘이 있는데 이 제목은 두 갈래 나무의 좌우 바늘로 앞뒤 바늘을 대체하고 두 갈래 검색 트리에서 정렬 쌍방향 체인표로의 전환을 완성한다.두 갈래 검색 트리가 중순으로 훑어보면 정렬에 해당한다.이 문제의 중점은 두루 돌아다니는 과정에서 좌우 바늘의 전환을 동시에 완성해야 한다는 데 있다.전체 과정을 두 단계로 나눈다. (1) 루트 노드와 정렬된 왼쪽 트리의 맨 오른쪽 노드를 연결한다. (2) 루트 노드와 정렬된 오른쪽 트리의 맨 왼쪽 노드를 연결한다. 이 과정은 귀속으로 실현할 수 있다.정렬된 양방향 체인 테이블 뒤에 액세스 노드를 추가하여 앞뒤 바늘의 전환을 완성하는 것과 같다.중순으로 두루 다니기 때문에 어릴 때부터 정렬에 이르렀다.
코드
class Solution {
public:
TreeNode* Convert(TreeNode* pRootOfTree){
if (pRootOfTree== nullptr)
return pRootOfTree;
TreeNode* lastNodeInList = nullptr; //
ConvertNode(pRootOfTree, &lastNodeInList); //
TreeNode* pHeadofList = lastNodeInList;
pHeadofList->right = nullptr;
while(pHeadofList->left!= nullptr)
pHeadofList = pHeadofList->left;
return pHeadofList;
}
// -》 -》
// ：
void ConvertNode(TreeNode* root, TreeNode** lastNodeInList){
if(root== nullptr)
return;
//
ConvertNode(root->left,lastNodeInList);
root->left = *lastNodeInList; //
if(*lastNodeInList != nullptr)
(*lastNodeInList)->right = root;
// ；
*lastNodeInList = root;
ConvertNode(root->right,lastNodeInList);
}
};
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
20200326 - 검지offer 면접문제 27: 두 갈래 나무의 거울이솔 위 안에 28문제의 답안이 있는데 어떻게 꼬치는지 모르겠다.간단해....
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
