이 진 트 리 고전 알고리즘 문제 정리
72965 단어 데이터 구조
이 진 트 리 시리즈 옮 겨 다 니 기:
4. 567917. 비 재 귀적 으로 이 진 트 리 의 앞 순 서 를 옮 겨 다 닌 다.사상: 창 고 를 만 들 고 팝 업 할 때마다 이 팝 업 결 과 를 저장 합 니 다.그리고 오른쪽, 왼쪽 나무의 뿌리 부분 을 창고 에 눌 러 주세요
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> r;
if (root==nullptr) return r;
stack<TreeNode*> q;
q.push(root);
while (!q.empty())
{
TreeNode* tmp = q.top();
q.pop();
r.push_back(tmp->val);
if (tmp->right) q.push(tmp->right);
if (tmp->left) q.push(tmp->left);
}
return r;
}
};
이 진 트 리 의 순서 가 옮 겨 다 닌 다.사상: 주의 하 세 요. 중간 순서 로 옮 겨 다 니 기 때문에 뿌리 노드 는 두 번 튕 겨 야 합 니 다. 첫 번 째 때 오른쪽 왼쪽 나무 에 계속 눌 러 야 합 니 다.두 번 째 시 결점 의 값 을 저장 합 니 다.핵심 은 pair 를 만들어 접근 횟수 를 저장 하 는 것 입 니 다
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> r;
if (!root) return r;
stack<pair<TreeNode*, int> > s;
s.push(make_pair(root, 0));
while (!s.empty())
{
pair<TreeNode*, int> tmp=s.top();
s.pop();
if (tmp.second==1 || ((tmp.first)->right==nullptr && (tmp.first)->left==nullptr) )
{r.push_back((tmp.first)->val);}
else if(tmp.second==0)
{
if ((tmp.first)->right) s.push(make_pair((tmp.first)->right,0));
tmp.second +=1;
s.push(tmp);
if ((tmp.first)->left) s.push(make_pair((tmp.first)->left,0));
}
}
return r;
}
};
4. 567917. 이 진 트 리 뒤에 순서대로 옮 겨 다 닌 다.사상: 중 서 와 같다.처음 팝 업 할 때 스 택 에 누 르 는 순서 가 다 를 뿐 입 니 다. 먼저 자신, 그리고 오른쪽, 그리고 왼쪽
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> r;
if (root==nullptr) return r;
stack<pair<TreeNode*, int>> s;
s.push(make_pair(root, 0));
while (!s.empty())
{
pair<TreeNode*, int> tmp = s.top();
s.pop();
if (tmp.second==1 || ((tmp.first)->left==nullptr && (tmp.first)->right==nullptr ))
r.push_back((tmp.first)->val);
else if(tmp.second==0)
{
tmp.second++;
s.push(tmp);
if ((tmp.first)->right) s.push(make_pair((tmp.first)->right, 0));
if ((tmp.first)->left) s.push(make_pair((tmp.first)->left, 0));
}
}
return r;
}
};
이 진 트 리 재 구축 시리즈:
4. 567917. 한 이 진 트 리 의 앞 순 서 를 입력 하고 중간 순 서 를 옮 겨 다 니 는 결 과 를 입력 하 십시오. 이 이 진 트 리 를 다시 만 드 십시오.입력 한 앞 순서 와 중간 순 서 를 옮 겨 다 니 는 결과 에 중복 되 는 숫자 가 없다 고 가정 합 니 다.사상: 앞 순 서 를 이용 하여 중간 순서 에 나타 난 점, 왼쪽 은 왼쪽 나무 이 고 오른쪽 은 오른쪽 나무 입 니 다.재 귀 법 으로 해결 하 다.
class Solution {
public:
TreeNode *reConstructBinaryTree(vector<int> pre,vector<int> in) {
TreeNode* root=reConstructBinaryTree(pre,0,pre.size()-1,in,0,in.size()-1);
return root;
}
// {1,2,4,7,3,5,6,8} {4,7,2,1,5,3,8,6}
private:
TreeNode *reConstructBinaryTree(vector<int> pre,int startPre,int endPre,vector<int> in,int startIn,int endIn) {
if(startPre>endPre||startIn>endIn)
return nullptr;
TreeNode *root=new TreeNode(pre[startPre]);
for(int i=startIn;i<=endIn;i++)
if(in[i]==pre[startPre]){
root->left=reConstructBinaryTree(pre,startPre+1,startPre+i-startIn,in,startIn,i-1);
root->right=reConstructBinaryTree(pre,i-startIn+startPre+1,endPre,in,i+1,endIn);
break;
}
return root;
}
};
4. 567917. 한 이 진 트 리 의 중간 순서 와 뒷 순 서 를 입력 하 십시오. 이 이 진 트 리 를 다시 만 드 십시오.입력 한 중간 순서 와 뒷 순 서 를 옮 겨 다 니 는 결과 에 중복 되 는 숫자 가 없다 고 가정 합 니 다.사상: 뒷 순 서 를 옮 겨 다 니 는 마지막 결점 은 뿌리 노드 입 니 다. 중간 순 서 를 옮 겨 다 니 면서 뿌리 노드 를 찾 을 수 있 습 니 다. 왼쪽 은 왼쪽 나무 이 고 오른쪽 은 오른쪽 나무 입 니 다.그 다음 에 뒤의 순서 에서 역방향 으로 찾 으 면 하위 나무의 뿌리 노드 를 얻 을 수 있 고 재 귀적 으로 얻 을 수 있 습 니 다
class Solution {
public:
TreeNode *reConstructBinaryTree(vector<int> pre,vector<int> in) {
TreeNode* root=reConstructBinaryTree(pre,0,pre.size()-1,in,0,in.size()-1);
return root;
}
private:
TreeNode *reConstructBinaryTree(vector<int> aft,int startAft,int endAft,vector<int> in,int startIn,int endIn) {
if(startAft>endAft||startIn>endIn)
return nullptr;
TreeNode *root=new TreeNode(aft[endAft]);
//
for(int i=startIn;i<=endIn;i++)
if(in[i]==aft[startAft]){
root->left=reConstructBinaryTree(aft,startAft,startAft+i-startIn,in,startIn,i-1);
root->right=reConstructBinaryTree(aft,i-startIn+startAft+1,endAft,in,i+1,endIn);
break;
//
}
return root;
}
};
4. 567917. 앞 순서 와 뒤 순 서 는 유일한 나무 구 조 를 보장 할 수 없다
이 진 트 리 의 층 차 를 옮 겨 다 닌 다.사고방식: 두 개의 대열 로 각 층 의 결점 을 교체 하여 기록 하고 외층 은 while 로 실현 하면 된다.for 문장의 첫 번 째 문장 은 초기 화 되 어 있 으 며, 다음 에는 실행 되 지 않 습 니 다
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
queue<TreeNode*> p, q;
vector<vector<int>> r;
if (root==nullptr) return r;
p.push(root);
while (!p.empty()||!q.empty())
{
vector<int> t1 ,t2;
if (!p.empty())
{
for (TreeNode *tmp = p.front();!p.empty();p.pop())
{
tmp = p.front();
if (tmp->left) q.push(tmp->left);
if (tmp->right) q.push(tmp->right);
t1.push_back(tmp->val);
}
r.push_back(t1);
}
if (!q.empty()){
for (TreeNode *tmp = q.front();!q.empty();q.pop())
{
tmp = q.front();
if (tmp->left) p.push(tmp->left);
if (tmp->right) p.push(tmp->right);
t2.push_back(tmp->val);
}
r.push_back(t2);
}
}
return r;
}
};
4.2 이 진 트 리 의 바닥 에서 위로 옮 겨 다 닌 다.대기 열 도 사용 할 수 있 습 니 다. 여 기 는 bfs 를 사용 하고 핵심 은 level 로 층 수 를 계산 한 다음 에 역방향 으로 삽입 하 는 것 입 니 다.
class Solution {
public:
vector<vector<int>> levelOrderBottom(TreeNode* root) {
vector<vector<int>> r;
helper(r, root,0);
return r;
}
void helper(vector<vector<int>> &r, TreeNode *p1, int level)
{
if (p1==nullptr) return;
if (level>=r.size()) {vector<int> tmp;r.insert(r.begin(), tmp);}
r[r.size()-1-level].push_back(p1->val);
helper(r, p1->left, level+1);
helper(r, p1->right, level+1);
}
};
이 진 트 리 의 톱니 모양 이 널리 퍼 져 있다.사고: 차원 과 차이 가 많 지 않 습 니 다. 스 택 으로 바 꾼 다음 에 두 번 째 스 택 에서 먼저 오른쪽 나무 에 밀어 넣 고 왼쪽 나무 에 밀어 넣 습 니 다
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
stack<TreeNode*> p, q;
vector<vector<int>> r;
if (root==nullptr) return r;
p.push(root);
while (!p.empty()||!q.empty())
{
vector<int> t1 ,t2;
if (!p.empty())
{
for (TreeNode *tmp = p.top();!p.empty();p.pop())
{
tmp = p.top();
if (tmp->left) q.push(tmp->left);
if (tmp->right) q.push(tmp->right);
t1.push_back(tmp->val);
}
r.push_back(t1);
}
if (!q.empty()){
for (TreeNode *tmp = q.top();!q.empty();q.pop())
{
tmp = q.top();
if (tmp->right) p.push(tmp->right);
if (tmp->left) p.push(tmp->left);
t2.push_back(tmp->val);
}
r.push_back(t2);
}
}
return r;
}
};
4. 567917. 이 진 트 리 와 양 방향 링크 사고: 중간 순서 로 옮 겨 다 니 는 사상.현재 노드 루트 에 대해 비어 있 으 면 nullptr 로 돌아 갑 니 다.그렇지 않 으 면 좌우 나무 에 대해 양 방향 체인 표 두 점 을 구하 세 요.왼쪽 나무 가 구 하 는 점 에 대해 오른쪽으로 끝까지 가서 루트, root - > left = 이 점 을 가리 킵 니 다.오른쪽 나무 에 대해 서 는 직접 가리 키 면 됩 니 다.재 귀, 마지막 으로 가장 왼쪽 결점 을 양 방향 링크 의 머리 결점 으로 되 돌려 줍 니 다
class Solution {
public:
TreeNode* find(TreeNode* root)
{
if (root==NULL) return NULL;
TreeNode*l = root;
while (l->right!=NULL)
l=l->right;
return l;
}
TreeNode* find2(TreeNode* root)
{
if (root==NULL) return NULL;
TreeNode*l = root;
while (l->left!=NULL)
l=l->left;
return l;
}
TreeNode* Convert(TreeNode* pRootOfTree)
{
TreeNode* t1, *t2=pRootOfTree;
if (pRootOfTree==NULL) return NULL;
while (t2->left!=NULL) t2=t2->left;
if (pRootOfTree->left!=NULL)
{
TreeNode *tmp=pRootOfTree->left;
TreeNode*s1=Convert(tmp);
t1=find(s1);
pRootOfTree->left=t1;
t1->right=pRootOfTree;
}
if (pRootOfTree->right!=NULL)
{
TreeNode* tmp=pRootOfTree->right;
TreeNode* s1=Convert(tmp);
pRootOfTree->right=s1;
s1->left=pRootOfTree;
}
return t2;
}
};
이 진 트 리 판별 시리즈:
4. 567917. 이 진 트 리 를 지정 하여 고도 의 균형 을 가 진 이 진 트 리 인지 판단 합 니 다.(좌우 두 나무의 높이 차 는 절대 1 을 초과 하지 않 는 다).사고: 고도 의 균형 을 판단 하려 면 당연히 고도 의 함 수 를 얻어 야 한다.높이 를 얻 는 것 외 에 나무 가 밸 런 스 트 리 가 아니라면 그 자체 도 밸 런 스 트 리 가 아니 라 는 점 을 고려 하여 하나의 상태 * - 1 * 로 표시 해 야 한다
class Solution {
public:
bool isBalanced(TreeNode* root) {
return getDepth(root)!=-1;
}
int getDepth(TreeNode *root)
{
if (root==nullptr) return 0;
int lh = getDepth(root->left), rh = getDepth(root->right);
if (lh == -1 || rh == -1 || abs(lh-rh)>1)
return -1;
return max(lh,rh)+1;
}
};
4. 567917. 비 공 이 진 트 리 s 와 t 를 지정 하고 s 에 t 와 같은 구조 와 노드 값 을 가 진 서브 트 리 가 포함 되 어 있 는 지 확인 합 니 다.사고방식: 먼저 동일 한 지 아 닌 지 를 판단 하 는 함 수 를 설계 해 야 한다.그 다음 에 이 함수 로 현재 가 같은 지 여 부 를 판단 합 니 다. 그렇지 않 으 면 왼쪽 트 리 와 오른쪽 트 리 로 돌아 갑 니 다.경계 조건 주의, nullptr..
class Solution {
public:
bool isSametree(TreeNode *a1, TreeNode *a2)
{
if (a1==nullptr&&a2!=nullptr) return false;
if (a2==nullptr&&a1!=nullptr) return false;
if (a1==nullptr&& a2==nullptr) return true;
return (a1->val==a2->val) && isSametree(a1->left, a2->left) && isSametree(a1->right, a2->right);
}
bool isSubtree(TreeNode* s, TreeNode* t) {
if(s==NULL && t!=NULL) return 0;
if(s!=NULL && t==NULL) return 0;
return (isSametree(s,t) || isSubtree(s->left,t) || isSubtree(s->right, t));// isSame? isSame 。
}
};
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
