除了鏈表，另一個面試常客莫屬二叉樹了，
鏈表面試題(動圖詳解)-明明做出來了卻為什么沒有Offer?
你已經是棵成熟的二叉樹了，要學會自己解題，

二叉樹的深度

題目：輸入一顆二叉樹的根節點，求該樹的的深度，
輸入一顆二叉樹的根節點，求該樹的深度，從根節點到葉節點依次經過的節點（含根、葉節點）形成的一條路徑，最長路徑的長度為樹的深度，

如果一棵樹只有一個節點，那么它的深度是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

二叉搜索樹的第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\n", test == nullptr ? -1 : test->val);
	test = check(root, 5);
	printf("第五個節點：%d\n", 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("\n");
}
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("\n");
}
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，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;
}
//運行結果：是子樹

（插播反爬資訊 ）博主CSDN地址：https://wzlodq.blog.csdn.net/

重建二叉樹

題目：輸入某二叉樹的前序遍歷和中序遍歷結果，請重建該二叉樹，假設輸入的前序遍歷和中序遍歷的結果中不含重復的數字，

在前序遍歷中，第一個數字總是樹的根節點的值，而在中序遍歷中，根節點的值在序列中間，左子樹節點的值位于根節點值得左邊，右子樹節點的值位于根節點值得右邊，因此需要掃描中序遍歷序列，才能找到根節點得值，

分別找到左、右子樹的前序和中序遍歷序列后，我們可以用同樣的方法分別構建左右子樹，即可以用遞回完成，

#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\n", test == nullptr ? -1 : test->val);
	test = getnext(p5);
	printf("節點5的下一個節點：%d\n", test == nullptr ? -1 : test->val);
	test = getnext(p8);
	printf("節點8的下一個節點：%d\n", test == nullptr ? -1 : test->val);
	test = getnext(p6);
	printf("節點6的下一個節點：%d\n", 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二叉搜索樹的后序序列\n", verify(a,7) ? "是" : "不是");
	int b[10] = { 3,4,1,2 };
	printf("陣列b%s二叉搜索樹的后序序列\n", 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("\n");
	}
	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\n",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
*/

原創不易，請勿轉載（本不富裕的訪問量雪上加霜 ）
博主首頁：https://wzlodq.blog.csdn.net/
微信公眾號：唔仄lo咚鏘
如果文章對你有幫助，記得一鍵三連?