자바 이 진 트 리 면접 문제 상세 설명

두 갈래 나무의 깊이
제목:이 진 트 리 의 뿌리 노드 를 입력 하여 나무의 깊이 를 구하 십시오.이 진 트 리 의 뿌리 노드 를 입력 하여 나무의 깊이 를 구하 십시오.뿌리 노드 에서 잎 노드 까지 순서대로 지나 가 는 노드(뿌리,잎 노드 포함)가 형 성 된 경로 로 가장 긴 경로 의 길 이 는 나무의 깊이 이다.
만약 에 한 그루 의 나무 가 한 노드 만 있다 면 그 깊이 는 1 이다.만약 에 뿌리 노드 가 왼쪽 나무 만 있다 면 그 깊이 는 왼쪽 나무의 깊이+1 이 고 같은 것 은 오른쪽 나무 만 있다 면 깊이 는 오른쪽 나무의 깊이+1 이다.만약 에 왼쪽 나무 와 오른쪽 나무 가 있다 면 두 나무의 깊이 최대 치+1 을 취하 면 된다.재 귀 를 이용 하면 실현 하기 쉽다.

#include<bits/stdc++.h>
using namespace std;
struct node {//     
	int val;
	node* left;//    
	node* right;//    
	node(int v, node* l=nullptr, node* r=nullptr) {
		val = v;
		left = l;
		right = r;
	}
};
int getDepth(node* root) {//     
	if (root == nullptr)
		return 0; //    0
	int l = getDepth(root->left);//     
	int r = getDepth(root->right);//     
	return max(l, r) + 1;//    +1
}
int main() {
	node* root = new node(1);//       
	node* l1 = root->left = new node(2);
	node* r1 = root->right = new node(3);
	l1->left = new node(4);
	l1->right = new node(5);
	r1->left = new node(6);
	r1->right = new node(7);
	printf("%d", getDepth(root));
	return 0;
}
//    ：3

실행 결과:
3
두 번 째 포크 검색 트 리 의 k 큰 노드
제목:이 진 트 리 를 지정 하여 K 큰 노드 를 찾 습 니 다.이 진 트 리 에서 왼쪽 노드 는 뿌리 노드 보다 작고 오른쪽 노드 는 뿌리 노드 보다 큽 니 다.
이 진 트 리 의 경우 중간 순 서 는 작은 것 에서 큰 것 으로 늘 어 나 는 순서 이기 때문에 이 진 트 리 의 순 서 를 검색 하면 K 큰 노드 를 쉽게 찾 을 수 있 습 니 다.

#include<bits/stdc++.h>
using namespace std;
struct node {//     
	int val;
	node* left;//    
	node* right;//    
	node(int v, node* l=nullptr, node* r=nullptr) {
		val = v;
		left = l;
		right = r;
	}
};
node* Kth(node* root, int &k) {
	node* ans = nullptr;
	if (root->left != nullptr)
		ans = Kth(root->left, k);
	if (ans == nullptr) {
		if (k == 1)
			ans = root;
		k--;
	}
	if (root->right != nullptr && ans == nullptr)
		ans = Kth(root->right, k);
	return ans;
}
node* check(node* root, int k) {//          
	if (k <= 0 || root == nullptr)
		return nullptr;
	return Kth(root, k);
}
int main() {
	node* root = new node(4);//         
	node* l1 = root->left = new node(2);
	node* r1 = root->right = new node(6);
	l1->left = new node(1);
	l1->right = new node(3);
	r1->left = new node(5);
	r1->right = new node(7);
	node* test = check(root, 1);
	printf("     ：%d
", test == nullptr ? -1 : test->val);
	test = check(root, 5);
	printf("     ：%d
", test == nullptr ? -1 : test->val);
	return 0;
}

실행 결과:
첫 번 째 노드:1 다섯 번 째 노드:5
위 에서 아래로 두 갈래 트 리 인쇄
제목:줄 을 나 누 지 않 고 위 에서 아래로 이 진 트 리 를 인쇄 합 니 다.위 에서 아래로 이 진 트 리 의 노드 를 인쇄 하고 같은 층 의 노드 는 왼쪽 에서 오른쪽으로 인쇄 합 니 다.

익숙 한 앞 뒤 순 서 를 옮 겨 다 니 거나 층 별로 옮 겨 다 니 는 것 과 는 다르다.한 노드 를 인쇄 할 때마다 이 노드 에 하위 노드 가 있 으 면 이 하위 노드 를 대열 의 끝 에 놓 습 니 다.다음은 대기 열의 머리 에서 가장 먼저 대기 열 에 들 어간 몇 가 지 를 꺼 내 고 앞의 인쇄 작업 을 반복 하 며 대기 열 에 있 는 모든 노드 가 인쇄 될 때 까지 합 니 다.bfs

#include<bits/stdc++.h>
using namespace std;
struct node {//     
	int val;
	node* left;//    
	node* right;//    
	node(int v, node* l=nullptr, node* r=nullptr) {
		val = v;
		left = l;
		right = r;
	}
};
void PrintFromTopToBottom(node* root) {//      
	if (root == nullptr)return;
	queue<node*>q;
	q.push(root);
	while (!q.empty()) {
		node* cur = q.front();
		q.pop();
		printf("%d ", cur->val);
		if (cur->left != nullptr)//    
			q.push(cur->left);
		if (cur->right != nullptr)
			q.push(cur->right);
	}
	printf("
");
}
int main() {
	node* root = new node(1);//       
	node* l1 = root->left = new node(2);
	node* r1 = root->right = new node(3);
	l1->left = new node(4);
	l1->right = new node(5);
	r1->left = new node(6);
	r1->right = new node(7);
	PrintFromTopToBottom(root);//  
	return 0;
}

실행 결과:
1 2 3 4 5 6 7
두 갈래 나무의 거울
제목:이 진 트 리 를 입력 하여 미 러 를 출력 합 니 다.

그림 분석 을 통 해 두 그루 의 나무 뿌리 노드 는 같 지만 좌우 부분 노드 는 위 치 를 교환 했다.지금 은 좌우 부분 노드 를 교환 한 다음 에 이 두 노드 의 좌우 부분 노드 위치 가 아직도 다르다 는 것 을 발견 했다.이렇게 돌아 가면 계속 교환 하면 된다.

#include<bits/stdc++.h>
using namespace std;
struct node {//     
	int val;
	node* left;//    
	node* right;//    
	node(int v, node* l=nullptr, node* r=nullptr) {
		val = v;
		left = l;
		right = r;
	}
};
void PrintFromTopToBottom(node* root) {//      
	if (root == nullptr)return;
	queue<node*>q;
	q.push(root);
	while (!q.empty()) {
		node* cur = q.front();
		q.pop();
		printf("%d ", cur->val);
		if (cur->left != nullptr)//    
			q.push(cur->left);
		if (cur->right != nullptr)
			q.push(cur->right);
	}
	printf("
");
}
void Mirror(node* root) {//     
	if (root == nullptr)
		return;
	if (root->left == nullptr && root->right == nullptr)
		return;
	swap(root->left, root->right);//       
	Mirror(root->left);//    
	Mirror(root->right);
}
int main() {
	node* root = new node(1);//       
	node* l1 = root->left = new node(2);
	node* r1 = root->right = new node(3);
	l1->left = new node(4);
	l1->right = new node(5);
	r1->left = new node(6);
	r1->right = new node(7);
	PrintFromTopToBottom(root);
	Mirror(root);
	PrintFromTopToBottom(root);
	return 0;
}

실행 결과:
1 2 3 4 5 6 7 1 3 2 7 6 5 4
대칭 적 인 이 진 트 리
제목:하나의 함 수 를 실현 하여 이 진 트 리 가 대칭 적 인지 아 닌 지 를 판단 한다.두 갈래 나무 가 거울 과 같다 면 그것 은 대칭 적 이다.

세 가지 옮 겨 다 니 는 방법 중(앞 순서,중간 순서 와 뒤 순서)은 모두 왼쪽 노드 를 옮 겨 다 니 며 오른쪽 노드 를 옮 겨 다 니 는 것 이다.만약 에 우리 가 먼저 오른쪽 노드 를 옮 겨 다 니 고 왼쪽 노드 를 옮 겨 다 닌 다음 에 앞 순서 의 왼쪽 과 오른쪽 을 비교 하면 대칭 여 부 를 판단 할 수 있다.
예 를 들 어 첫 번 째 나무 앞 순 서 는 왼쪽,오른쪽:{1,2,3,2,4,3},앞 순 서 는 오른쪽,왼쪽:{1,2,3,4,2,4,3},두 서열 이 같 으 면 대칭 으로 판단 할 수 있다.
예 를 들 어 두 번 째 나무 앞 순 서 는 왼쪽,오른쪽:{1,2,3,4,2,4,5},앞 순 서 는 오른쪽,왼쪽:{1,2,5,4,2,4,3},두 서열 이 다 르 면 비대 칭 이다.
그러나 세 번 째 나무의 상황 에 주의 하 세 요.둘 다{1,2,2,2}이지 만 분명히 옳지 않 기 때문에 상공 지침 을 넣 어 판단 해 야 합 니 다.앞 순 서 는 왼쪽,뒤 오른쪽:{1,2,null,null,2,null,null},앞 순 서 는 오른쪽,뒤 왼쪽:{1,2,null,null,2,null,2},그리고 비대 칭 으로 판단 합 니 다.

#include<bits/stdc++.h>
using namespace std;
struct node {//     
	int val;
	node* left;//    
	node* right;//    
	node(int v, node* l=nullptr, node* r=nullptr) {
		val = v;
		left = l;
		right = r;
	}
};
bool isSymmetrical(node* r1, node* r2) {//          
	if (r1 == nullptr && r2 == nullptr)
		return true;
	if (r1 == nullptr || r2 == nullptr)
		return false;
	if (r1->val != r2->val)
		return false;
	return isSymmetrical(r1->left, r2->right)
		&& isSymmetrical(r1->right, r2->left);
}
bool isSymmetrical(node* root) {//         
	return isSymmetrical(root, root);
}
int main() {
	node* root = new node(1);//         
	node* l1 = root->left = new node(2);
	node* r1 = root->right = new node(2);
	l1->left = new node(3);
	l1->right = new node(4);
	r1->left = new node(4);
	r1->right = new node(3);
	if (isSymmetrical(root))
		printf("  ");
	else 
		printf("   ");
	return 0;
}

실행 결과:
대칭
나무의 서브 구조
제목:이 진 A 와 B 두 개 를 입력 하여 B 가 A 의 서브 구조 인지 아 닌 지 를 판단 한다.

우 리 는 두 단계 로 나 눌 수 있다.먼저 뿌리 노드 의 값 이 같은 노드 를 찾 은 다음 에 이 노드 를 뿌리 노드 로 하 는 서브 트 리 가 같은 구 조 를 포함 하 는 지 판단 할 수 있다.사실 주로 나무의 역 사 를 살 펴 보고 재 귀적 으로 완성 할 수 있다.

#include<bits/stdc++.h>
using namespace std;
struct node {//     
	int val;
	node* left;//    
	node* right;//    
	node(int v, node* l=nullptr, node* r=nullptr) {
		val = v;
		left = l;
		right = r;
	}
};
bool check(node* r1, node* r2) {
	if (r2 == nullptr)
		return true; //     
	if (r1 == nullptr)
		return false;
	if (r1->val != r2->val)
		return false;
	return check(r1->left, r2->left) && check(r1->right, r2->right);
}
bool HasSubtree(node* r1, node* r2) {
	bool ans = false;
	if (r1 != nullptr && r2 != nullptr) {
		if (r1->val == r2->val) //        
			ans = check(r1, r2);//            
		if (ans == false) //  ，            
			ans = HasSubtree(r1->left, r2);
		if (ans == false)
			ans = HasSubtree(r1->right, r2);
	}
	return ans;
}
int main() {
	node* root = new node(1);//       
	node* l1 = root->left = new node(2);
	node* r1 = root->right = new node(1);
	l1->left = new node(4);
	l1->right = new node(3);
	r1->left = new node(2);
	r1->right = new node(3);
	node* part = new node(1);//    
	part->left = new node(2);
	part->right = new node(3);
	if (HasSubtree(root, part))
		printf("   ");
	else
		printf("    ");
	return 0;
}

실행 결과:
자나무
이 진 트 리 재건
제목:한 이 진 트 리 의 앞 순 서 를 입력 하고 중간 순 서 를 옮 겨 다 니 는 결 과 를 입력 하 십시오.이 이 진 트 리 를 다시 만 드 십시오.입력 한 앞 순 서 를 옮 겨 다 니 는 결과 에 중복 되 는 숫자 가 없다 고 가정 하 십시오.
앞의 순서 에서 첫 번 째 숫자 는 나무의 뿌리 노드 의 값 이 고 중간 순서 에서 뿌리 노드 의 값 은 서열 중간 에 있 으 며 왼쪽 서브 트 리 노드 의 값 은 뿌리 노드 가 왼쪽 에 있 고 오른쪽 서브 트 리 노드 의 값 은 뿌리 노드 가 오른쪽 에 있 기 때문에 중간 순서 로 서열 을 옮 겨 다 녀 야 뿌리 노드 의 값 을 찾 을 수 있 습 니 다.

왼쪽,오른쪽 트 리 의 앞 순서 와 중간 순 서 를 각각 찾 은 후에 우 리 는 똑 같은 방법 으로 좌우 트 리 를 각각 구축 할 수 있다.즉,재 귀적 으로 완성 할 수 있다.

#include<bits/stdc++.h>
using namespace std;
struct node {//     
	int val;
	node* left;//    
	node* right;//    
	node(int v, node* l=nullptr, node* r=nullptr) {
		val = v;
		left = l;
		right = r;
	}
};
//    ：      、      、      、      
node* Construct(int* startPre,int* endPre,int* startIn,int* endIn) {//       
	int rootVal = startPre[0];//           
	node* root = new node(rootVal);
	if (startPre == endPre) { //    ：     
		if (startIn == endIn && *startPre == *startIn)
			return root;
		//else throw exception();//             
	}
	int* rootIn = startIn; //             
	while (rootIn <= endIn && *rootIn != rootVal)
		rootIn++;
	//if (rootIn == endIn && *rootIn != rootVal)
	//	throw exception();//      
	int leftLen = rootIn - startIn;//     
	int* leftPreEnd = startPre + leftLen;
	if (leftLen > 0) { //     
		root->left = Construct(startPre + 1, leftPreEnd, startIn, rootIn - 1);
	}
	if (leftLen < endPre - startPre) {//     
		root->right = Construct(leftPreEnd + 1, endPre, rootIn + 1, endIn);
	}
	return root;
}
void post(node* root) {//      
	if (root == nullptr)return;
	post(root->left);
	post(root->right);
	printf("%d ", root->val);
}
int main() {
	int pre[10] = { 1,2,4,3,5,7,6,8 };
	int in[10] = { 2,4,1,7,5,3,6,8 };
	node* p = Construct(pre, pre + 7, in, in + 7);
	post(p);//      
	return 0;
}

실행 결과:
4 2 7 5 8 6 3 1
이 진 트 리 의 다음 노드
제목:이 진 트 리 와 그 중의 한 노드 를 지정 하고 중간 순서 로 서열 을 옮 겨 다 니 는 다음 노드 를 어떻게 찾 습 니까?나무의 노드 는 좌우 노드 를 가리 키 는 두 개의 지침 을 제외 하고 부모 노드 를 가리 키 는 지침 도 있다.
사실은 중 서 를 옮 겨 다 니 는 이 해 를 고찰 하 는 것 이다.먼저 아래 를 고려 해 보 세 요.중간 순서 에 있 는 다음 노드 는 왼쪽 하위 트 리 에서 고려 할 수 없습니다.따라서 한 노드 에 오른쪽 하위 트 리 가 있다 면 다음 노드 는 오른쪽 하위 트 리 의 가장 왼쪽 노드 입 니 다.
그 다음 에 위로(즉 오른쪽 서브 트 리 가 없 음)를 고려 합 니 다.만약 에 노드 가 그의 부모 노드 의 왼쪽 서브 노드 라면 그의 다음 노드 는 바로 그의 부모 노드 입 니 다.노드 가 부모 노드 의 오른쪽 부분 노드 라면 부모 노드 를 가리 키 는 지침 을 따라 위로 옮 겨 다 니 며 부모 노드 의 왼쪽 부분 노드 를 찾 아야 합 니 다.만약 에 존재 한다 면 이 노드 의 부모 노드 는 답 이다.그렇지 않 으 면 그 는 마지막 노드 이 고 다음 노드 가 없다.
같은 앞 순서,뒤 순서 의 다음 노드 는 같은 이치 로 하 나 를 들 면 열 을 안다.

#include<bits/stdc++.h>
using namespace std;
struct node {//     
	int val;
	node* left;//    
	node* right;//    
	node* parent;//   
	node(int v,node*p=nullptr) {
		val = v;
		left = nullptr;
		right = nullptr;
		parent = p;
	}
};
node* getnext(node* p) {
	if (p == nullptr)
		return nullptr;
	node* next = nullptr;
	if (p->right != nullptr) {//    
		node* r = p->right;//   
		while (r->left != nullptr)
			r = r->left;
		next = r;
	}
	else if(p->parent!=nullptr){//         
		node* cur = p;
		node* par = p->parent;
		while (par != nullptr && cur == par->right) {
			cur = par; //                 
			par = par->parent;
		}
		next = par;
	}
	return next;
}
int main() {
	node* root = new node(1);//  
	node* p2 = new node(2,root);
	node* p4 = new node(4, p2);
	p2->right = p4;
	node* p7 = new node(7, p4);
	node* p8 = new node(8, p4);
	p4->left = p7, p4->right = p8;
	node* p3 = new node(3, root);
	root->left = p2, root->right = p3;
	node* p5 = new node(5, p3);
	node* p6 = new node(6, p3);
	p3->left = p5, p3->right = p6;
	node* test = getnext(p4);
	printf("  4      ：%d
", test == nullptr ? -1 : test->val);
	test = getnext(p5);
	printf("  5      ：%d
", test == nullptr ? -1 : test->val);
	test = getnext(p8);
	printf("  8      ：%d
", test == nullptr ? -1 : test->val);
	test = getnext(p6);
	printf("  6      ：%d
", test == nullptr ? -1 : test->val);
	return 0;
}

실행 결 과 는 다음 과 같 습 니 다.
노드 4 의 다음 노드:8 노드 5 의 다음 노드:3 노드 8 의 다음 노드:1 노드 6 의 다음 노드:-1
두 갈래 검색 트 리 의 뒷 순 서 를 옮 겨 다 니 는 경로
제목:정수 배열 을 입력 하여 이 배열 이 어떤 이 진 트 리 의 뒤 순 서 를 옮 겨 다 니 는 지 판단 합 니 다.입력 한 배열 의 임의의 두 숫자 가 다르다 고 가정 합 니 다.
뒷 순 서 를 옮 겨 다 니 는 과정 에서 마지막 노드 는 뿌리 노드 이 고 이 진 트 리 이기 때문에 왼쪽 트 리 는 그것 보다 작고 오른쪽 트 리 는 그것 보다 크기 때문에 좌우 트 리 두 부분 을 나 눌 수 있다.그 다음 에 분 단 된 트 리 에서 똑 같이 마지막 으로 뿌리 노드 이 고 재 귀적 으로 처리 하면 된다.
사실은 이 진 트 리 의 은밀 한 조건 을 통 해 이 진 트 리 의 뒷 순서 와 중 서 를 통 해 나 무 를 지 을 수 있 는 지 를 구 하 는 것 과 같다.앞에서 이 진 트 리 를 재건 하 는 문제 와 국 을 바 꾸 고 약 을 바 꾸 지 않 는 다.

#include<bits/stdc++.h>
using namespace std;
struct node {//     
	int val;
	node* left;//    
	node* right;//    
	node(int v, node* l = nullptr, node* r = nullptr) {
		val = v;
		left = l;
		right = r;
	}
};
bool verify(int s[], int len) {
	if (len <= 0 || s == nullptr)
		return false;
	int root = s[len - 1];//   
	int i = 0;
	while (i < len - 1) {//            
		if (s[i] > root)
			break;
		i++;
	}
	int j = i;
	while (j < len - 1) {
		if (s[j++] < root)
			return false;
	}
	bool l = true, r = true;
	if (i > 0)//     
		l = verify(s, i);
	if (i < len - 1)//     
		r = verify(s + i, len - i - 1);
	return (l && r);
}
int main() {
	int a[10] = { 1,3,2,5,7,6,4 };
	printf("  a%s          
", verify(a,7) ? " " : "  ");
	int b[10] = { 3,4,1,2 };
	printf("  b%s          
", verify(b, 4) ? " " : "  ");
	return 0;
}

실행 결 과 는 다음 과 같 습 니 다.
배열 a 는 이 진 트 리 의 백 시퀀스 입 니 다.배열 b 는 이 진 트 리 의 백 시퀀스 가 아 닙 니 다.
이 진 트 리 와 특정한 값 의 경로
제목:이 진 트 리 와 정 수 를 입력 하고 이 진 트 리 의 노드 값 과 정 수 를 입력 하기 위 한 모든 경 로 를 출력 합 니 다.나무의 뿌리 노드 부터 잎 노드 가 지나 가 는 노드 까지 하나의 경 로 를 형성한다.
먼저 경로 의 정 의 는 뿌리 노드 에서 잎 노드 까지 이 고 앞 순서 만 이 뿌리 노드 에 먼저 접근 하기 때 문 입 니 다.현재 순서 가 특정한 노드 에 접근 할 때 우 리 는 이 노드 를 경로 에 추가 하고 이 노드 의 값 을 누적 합 니 다.만약 에 노드 가 잎 노드 라면 이때 누적 값 이 입력 정수 에 부합 되 는 지 판단 하고 일치 하면 출력 경 로 를 판단 합 니 다.방문 이 끝 난 후에 경로 에서 이 노드 를 삭제 하고 이 노드 의 값 을 빼 야 합 니 다.간단 한 dfs 입 니 다.

#include<bits/stdc++.h>
using namespace std;
struct node {//     
	int val;
	node* left;//    
	node* right;//    
	node(int v, node* l = nullptr, node* r = nullptr) {
		val = v;
		left = l;
		right = r;
	}
};
void dfs(node* root, vector<int>path,int sum,int cur) {
	if (root == nullptr)
		return;
	cur += root->val;
	path.push_back(root->val);
	if (cur == sum && root->left == nullptr && root->right == nullptr) {
		//        
		for (int i = 0; i < path.size(); i++)
			printf("%d ", path[i]);
		printf("
");
	}
	dfs(root->left, path, sum, cur);
	dfs(root->right, path, sum, cur);
	path.pop_back();//  
}
int main() {
	node* root = new node(10);
	node* l = root->left = new node(3);
	root->right = new node(5);
	l->left = new node(-2);
	l->right = new node(2);
	vector<int>v;
	dfs(root, v, 15, 0);
	return 0;
}

실행 결 과 는 다음 과 같 습 니 다.
10 3 2 10 5
이 진 트 리 와 양 방향 링크 검색
제목:이 진 트 리 를 입력 하고 이 진 트 리 를 정렬 된 양 방향 링크 로 변환 합 니 다.새로운 노드 를 만 들 수 없고 책 에 있 는 노드 포인터 의 방향 만 조정 할 수 있 습 니 다.

이 진 트 리 의 왼쪽 노드 는 부모 노드 보다 작고 오른쪽 노드 는 부모 노드 보다 크기 때문에 원래 왼쪽 노드 를 가리 키 는 지침 을 목록 에서 앞의 노드 를 가리 키 는 지침 으로 조정 할 수 있 습 니 다.원래 오른쪽 노드 를 가리 키 는 지침 을 다음 노드 를 가리 키 는 지침 으로 조정 할 수 있 습 니 다.
전 환 된 체인 테이블 은 정렬 된 순서 이기 때문에 우 리 는 나무의 노드 를 중간 순서 로 옮 길 수 있다.뿌리 노드 에 옮 겨 다 니 면 나 무 를 세 부분 으로 뜯 을 수 있다.4 번 노드,뿌리 노드 가 2 인 왼쪽 나무,뿌리 노드 가 6 인 오른쪽 나 무 를 뜯 을 수 있다.또한 정의 에 따라 왼쪽 하위 트 리 의 최대 노드 와 연결 하고 오른쪽 하위 트 리 의 최소 노드 와 연결 합 니 다.이때 의 왼쪽 나 무 는 마치 정렬 된 링크 와 같 습 니 다.이어서 오른쪽 나 무 를 옮 겨 다 니 면 되 지만 다시 돌아 가 는 것 이 아 닙 니까?

#include<bits/stdc++.h>
using namespace std;
struct node {//     
	int val;
	node* left;//    
	node* right;//    
	node(int v, node* l = nullptr, node* r = nullptr) {
		val = v;
		left = l;
		right = r;
	}
};
void dfs(node* p, node** t) {
	if (p == nullptr)
		return;
	node* cur = p;//  
	if (cur->left != nullptr)//  
		dfs(cur->left, t);
	cur->left = *t;//                 
	if (*t != nullptr)
		(*t)->right = cur;//                 
	*t = cur;//        
	if (cur->right != nullptr)
		dfs(cur->right, t);
}
node* toList(node* root) {
	node* tail = nullptr;//         
	dfs(root, &tail);
	node* head = tail; //   
	while (head != nullptr && head->left != nullptr)
		head = head->left; //left     
	return head;
}
int main() {
	node* root = new node(4);//         
	node* l = root->left = new node(2);
	l->left = new node(1);
	l->right = new node(3);
	node* r = root->right = new node(6);
	r->left = new node(5);
	r->right = new node(7);
	node* list = toList(root);
	while (list->right != nullptr) {
		printf("%d ", list->val);
		list = list->right;
	}
	printf("%d
",list->val);
	while (list != nullptr) {
		printf("%d ", list->val);
		list = list->left;
	}
	return 0;

실행 결과:
1 2 3 4 5 6 7 7 6 5 4 3 2 1
총결산
이 글 은 여기까지 입 니 다.당신 에 게 도움 을 줄 수 있 기 를 바 랍 니 다.또한 당신 이 우리 의 더 많은 내용 에 관심 을 가 져 주 실 수 있 기 를 바 랍 니 다!