두 갈래 나무에서 두 개의 결점을 찾는 최근 공공 조상의 결점
1490 단어 알고리즘과 데이터 구조
2. 삼차 체인(부부 노드를 찾을 수 있음): 4개 노드에서 루트 결점까지 두루 돌아다니며 첫 번째와 7개 결점에서 루트 결점까지의 경로가 겹치는 결점을 찾아낸다.(각각 4, 3, 5, 10이 7-8-5-10에 있는지, 5가 가장 먼저 겹치기 때문에 5가 4와 7 조상의 결점이다)
3. 일반 두 갈래 나무: 먼저 뿌리 결점을 찾아 a, b 결점까지의 경로를 반복해서 수조에 저장한 다음에 두 수조를 반복해서 두 수조의 첫 번째 다른 결점의 이전 결점을 찾아낸다.
#pragma once
#include
using namespace std;
#include
struct Node
{
Node* left;
Node *right;
int value;
Node(int v)
:left(NULL)
,right(NULL)
,value(v)
{}
};
bool GetPath(Node *root,vector&path,Node* x)
{
if (root == NULL)
{
return false;
}
path.push_back(root);
if (root == x)
{
return true;
}
if (GetPath(root->left, path, x))
{
return true;
}
if (GetPath(root->right, path, x))
{
return true;
}
else
{
path.pop_back();
return false;
}
}
Node* find_common_parent(Node* root, Node* a, Node* b)
{
if (root == NULL)
{
return NULL;
}
Node* common_parent = NULL;
vector va, vb;
GetPath(root, va, a);
GetPath(root, vb, b);
size_t i = 0;
while (i < va.size() && i < vb.size() && va[i] == vb[i])
{
common_parent = va[i];
i++;
}
return common_parent;
} 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Python3를 사용하여 빠른 배열 정렬2020년 새해 복 많이 받으세요.저는 ryuichi69라고 합니다.오늘도 알고리즘 연습의 성과, 연습을 설명하는 동시에 이 글을 썼다.솔직히 이해하기 쉽게 쓰느라 힘들었는데 설명하기 어려운 부분, 요건 누락 등이 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
