java二叉樹(shù)面試題詳解
二叉樹(shù)的深度
題目：輸入一顆二叉樹(shù)的根節(jié)點(diǎn)，求該樹(shù)的的深度。輸入一顆二叉樹(shù)的根節(jié)點(diǎn)，求該樹(shù)的深度。從根節(jié)點(diǎn)到葉節(jié)點(diǎn)依次經(jīng)過(guò)的節(jié)點(diǎn)（含根、葉節(jié)點(diǎn)）形成的一條路徑，最長(zhǎng)路徑的長(zhǎng)度為樹(shù)的深度。
如果一棵樹(shù)只有一個(gè)節(jié)點(diǎn)，那么它的深度是1.如果根節(jié)點(diǎn)只有左子樹(shù)，那深度是其左子樹(shù)的深度+1，同樣的只有右子樹(shù)的話，深度是其右子樹(shù)深度+1，如果既有左子樹(shù)又有右子樹(shù)，取兩個(gè)子樹(shù)的深度最大值+1即可。用遞歸很容易實(shí)現(xiàn)。
#include<bits/stdc++.h>
using namespace std;
struct node {//樹(shù)節(jié)點(diǎn)定義
int val;
node* left;//左子節(jié)點(diǎn)
node* right;//右子節(jié)點(diǎn)
node(int v, node* l=nullptr, node* r=nullptr) {
val = v;
left = l;
right = r;
}
};
int getDepth(node* root) {//獲取樹(shù)深度
if (root == nullptr)
return 0; //為空返回0
int l = getDepth(root->left);//左子樹(shù)深度
int r = getDepth(root->right);//右子樹(shù)深度
return max(l, r) + 1;//取最大的+1
}
int main() {
node* root = new node(1);//構(gòu)建一顆二叉樹(shù)
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;
}
//運(yùn)行結(jié)果：3
運(yùn)行結(jié)果：
3
二叉搜索樹(shù)的第k大節(jié)點(diǎn)
題目：給定一顆二叉搜索樹(shù)，找出其中第k大節(jié)點(diǎn)。注意二叉搜索樹(shù)中，左節(jié)點(diǎn)比根節(jié)點(diǎn)小，右節(jié)點(diǎn)比根節(jié)點(diǎn)大。
對(duì)于二叉搜索樹(shù)來(lái)說(shuō)，它的中序遍歷就是從小到大遞增的序列，因此只需要對(duì)二叉搜索樹(shù)中序遍歷，就能很容易找到它的第k大節(jié)點(diǎn)。
#include<bits/stdc++.h>
using namespace std;
struct node {//樹(shù)節(jié)點(diǎn)定義
int val;
node* left;//左子節(jié)點(diǎn)
node* right;//右子節(jié)點(diǎn)
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);//構(gòu)建一顆二叉搜索樹(shù)
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("第一個(gè)節(jié)點(diǎn)：%d\n", test == nullptr ? -1 : test->val);
test = check(root, 5);
printf("第五個(gè)節(jié)點(diǎn)：%d\n", test == nullptr ? -1 : test->val);
return 0;
}
運(yùn)行結(jié)果：
第一個(gè)節(jié)點(diǎn)：1 第五個(gè)節(jié)點(diǎn)：5
從上到下打印二叉樹(shù)
題目：不分行從上到下打印二叉樹(shù)。從上到下打印二叉樹(shù)的那個(gè)節(jié)點(diǎn)，同一層的節(jié)點(diǎn)按照從左到右的順序打印。
不同于熟悉的前中后序遍歷或按層遍歷。每次打印一個(gè)節(jié)點(diǎn)的時(shí)候，如果該節(jié)點(diǎn)有子節(jié)點(diǎn)，則把該子節(jié)點(diǎn)放到一個(gè)隊(duì)列的隊(duì)尾。接下來(lái)到隊(duì)列的頭部取出最早進(jìn)入隊(duì)列的幾點(diǎn)，重復(fù)前面的打印操作，直到隊(duì)列中所有節(jié)點(diǎn)都被打印出來(lái)。即就是一個(gè)bfs。
#include<bits/stdc++.h>
using namespace std;
struct node {//樹(shù)節(jié)點(diǎn)定義
int val;
node* left;//左子節(jié)點(diǎn)
node* right;//右子節(jié)點(diǎn)
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);//構(gòu)建一顆二叉樹(shù)
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);//調(diào)用
return 0;
}
運(yùn)行結(jié)果：
1 2 3 4 5 6 7
二叉樹(shù)的鏡像
題目：輸入一顆二叉樹(shù)，輸出它的鏡像。
通過(guò)畫(huà)圖分析，兩棵樹(shù)根節(jié)點(diǎn)相同，但左右子節(jié)點(diǎn)交換了位置，現(xiàn)在交換左右子節(jié)點(diǎn)，然后發(fā)現(xiàn)這兩個(gè)節(jié)點(diǎn)的左右子節(jié)點(diǎn)位置還是不同，如此遞歸下去一直交換即可。
#include<bits/stdc++.h>
using namespace std;
struct node {//樹(shù)節(jié)點(diǎn)定義
int val;
node* left;//左子節(jié)點(diǎn)
node* right;//右子節(jié)點(diǎn)
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) {//鏡像二叉樹(shù)
if (root == nullptr)
return;
if (root->left == nullptr && root->right == nullptr)
return;
swap(root->left, root->right);//交換左右子節(jié)點(diǎn)
Mirror(root->left);//遞歸下去
Mirror(root->right);
}
int main() {
node* root = new node(1);//構(gòu)建一顆二叉樹(shù)
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;
}
運(yùn)行結(jié)果：
1 2 3 4 5 6 7 1 3 2 7 6 5 4
對(duì)稱(chēng)的二叉樹(shù)
題目：實(shí)現(xiàn)一個(gè)函數(shù)，用來(lái)判斷一顆二叉樹(shù)是不是對(duì)稱(chēng)的。如果一顆二叉樹(shù)和它的鏡像一樣，那么它就是對(duì)稱(chēng)的。
在三種遍歷方法中（前序、中序和后序）都是先遍歷左節(jié)點(diǎn)在遍歷右節(jié)點(diǎn)，如果我們先遍歷右節(jié)點(diǎn)再遍歷左節(jié)點(diǎn)，然后再和前序的先左后右比較，就可以判斷是否對(duì)稱(chēng)了。
比如第一棵樹(shù)前序先左后右：{1，2，3，2，4，3}，前序先右后左：{1，2，3，4，2，4，3}，兩序列一樣，即可判為對(duì)稱(chēng)。
如第二棵樹(shù)前序先左后右：{1，2，3，4，2，4，5}，前序先右后左：{1，2，5，4，2，4，3}，兩序列不同，即不對(duì)稱(chēng)。
但注意第三棵樹(shù)情況，兩者都是{1，2，2，2}但明顯是不對(duì)成的，故需要加上空指針來(lái)判斷。前序先左后右：{1，2，2，null，null，2，null，null}，前序先右后左：{1，2，null，null，2，null，2}，然后判斷為不對(duì)稱(chēng)。
#include<bits/stdc++.h>
using namespace std;
struct node {//樹(shù)節(jié)點(diǎn)定義
int val;
node* left;//左子節(jié)點(diǎn)
node* right;//右子節(jié)點(diǎn)
node(int v, node* l=nullptr, node* r=nullptr) {
val = v;
left = l;
right = r;
}
};
bool isSymmetrical(node* r1, node* r2) {//即兩棵樹(shù)是否互為鏡像
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) {//判斷一棵樹(shù)是否對(duì)稱(chēng)
return isSymmetrical(root, root);
}
int main() {
node* root = new node(1);//構(gòu)建一顆對(duì)稱(chēng)二叉樹(shù)
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("對(duì)稱(chēng)");
else
printf("不對(duì)稱(chēng)");
return 0;
}
運(yùn)行結(jié)果：
對(duì)稱(chēng)
樹(shù)的子結(jié)構(gòu)
題目：輸入兩顆二叉A和B，判斷B是不是A的子結(jié)構(gòu)。
我們可以分成兩步，首先找到根節(jié)點(diǎn)值一樣的節(jié)點(diǎn)，然后判斷以該節(jié)點(diǎn)為根節(jié)點(diǎn)的子樹(shù)是否包含一樣的結(jié)構(gòu)。其實(shí)主要還是考察樹(shù)的遍歷，用遞歸即可完成。
#include<bits/stdc++.h>
using namespace std;
struct node {//樹(shù)節(jié)點(diǎn)定義
int val;
node* left;//左子節(jié)點(diǎn)
node* right;//右子節(jié)點(diǎn)
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) //找到值相同的節(jié)點(diǎn)
ans = check(r1, r2);//然后判斷是否包含一樣結(jié)構(gòu)
if (ans == false) //剪枝，是子結(jié)構(gòu)就不必再繼續(xù)找了
ans = HasSubtree(r1->left, r2);
if (ans == false)
ans = HasSubtree(r1->right, r2);
}
return ans;
}
int main() {
node* root = new node(1);//構(gòu)建一顆二叉樹(shù)
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);//構(gòu)建子樹(shù)
part->left = new node(2);
part->right = new node(3);
if (HasSubtree(root, part))
printf("是子樹(shù)");
else
printf("不是子樹(shù)");
return 0;
}
運(yùn)行結(jié)果：
是子樹(shù)
重建二叉樹(shù)
題目：輸入某二叉樹(shù)的前序遍歷和中序遍歷結(jié)果，請(qǐng)重建該二叉樹(shù)，假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中不含重復(fù)的數(shù)字。
在前序遍歷中，第一個(gè)數(shù)字總是樹(shù)的根節(jié)點(diǎn)的值，而在中序遍歷中，根節(jié)點(diǎn)的值在序列中間，左子樹(shù)節(jié)點(diǎn)的值位于根節(jié)點(diǎn)值得左邊，右子樹(shù)節(jié)點(diǎn)的值位于根節(jié)點(diǎn)值得右邊，因此需要掃描中序遍歷序列，才能找到根節(jié)點(diǎn)得值。
分別找到左、右子樹(shù)的前序和中序遍歷序列后，我們可以用同樣的方法分別構(gòu)建左右子樹(shù)，即可以用遞歸完成。
#include<bits/stdc++.h>
using namespace std;
struct node {//樹(shù)節(jié)點(diǎn)定義
int val;
node* left;//左子節(jié)點(diǎn)
node* right;//右子節(jié)點(diǎn)
node(int v, node* l=nullptr, node* r=nullptr) {
val = v;
left = l;
right = r;
}
};
//四個(gè)參數(shù)：前序開(kāi)始位置、前序結(jié)束位置、中序開(kāi)始位置、中序結(jié)束位置
node* Construct(int* startPre,int* endPre,int* startIn,int* endIn) {//根據(jù)前中序建樹(shù)
int rootVal = startPre[0];//根節(jié)點(diǎn)是前序遍歷第一個(gè)
node* root = new node(rootVal);
if (startPre == endPre) { //遞歸出口：只一個(gè)節(jié)點(diǎn)
if (startIn == endIn && *startPre == *startIn)
return root;
//else throw exception();//若輸入不確保正確則拋出異常
}
int* rootIn = startIn; //在中序遍歷中找到根節(jié)點(diǎn)的值
while (rootIn <= endIn && *rootIn != rootVal)
rootIn++;
//if (rootIn == endIn && *rootIn != rootVal)
// throw exception();//找不到拋異常
int leftLen = rootIn - startIn;//左子樹(shù)長(zhǎng)度
int* leftPreEnd = startPre + leftLen;
if (leftLen > 0) { //構(gòu)建左子樹(shù)
root->left = Construct(startPre + 1, leftPreEnd, startIn, rootIn - 1);
}
if (leftLen < endPre - startPre) {//構(gòu)建右子樹(shù)
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;
}
運(yùn)行結(jié)果：
4 2 7 5 8 6 3 1
二叉樹(shù)的下一個(gè)節(jié)點(diǎn)
題目：給定一顆二叉樹(shù)和其中一個(gè)節(jié)點(diǎn)，如何找出中序遍歷序列的下一個(gè)節(jié)點(diǎn)？樹(shù)中的節(jié)點(diǎn)除了有兩個(gè)分別指向左右節(jié)點(diǎn)的指針，還有一個(gè)指向父節(jié)點(diǎn)的指針。
其實(shí)是考察對(duì)中序遍歷的理解。首先向下考慮，中序遍歷中它的下一個(gè)節(jié)點(diǎn)不可能在左子樹(shù)中考慮，所以如果一個(gè)節(jié)點(diǎn)有右子樹(shù)，那么它的下一個(gè)節(jié)點(diǎn)就是它右子樹(shù)中的最左節(jié)點(diǎn)。
其次向上考慮（即無(wú)右子樹(shù)），如果節(jié)點(diǎn)是它父節(jié)點(diǎn)的左子節(jié)點(diǎn)，那么它的下一個(gè)節(jié)點(diǎn)就是它的父節(jié)點(diǎn)。如果節(jié)點(diǎn)是它父節(jié)點(diǎn)的右子節(jié)點(diǎn)，這時(shí)就需要沿著指向父節(jié)點(diǎn)的指針一直向上遍歷，直到找到一個(gè)是它父節(jié)點(diǎn)的左子節(jié)點(diǎn)的節(jié)點(diǎn)。如果存在則這個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)是答案，否則他就是最后一個(gè)節(jié)點(diǎn)，無(wú)下一個(gè)節(jié)點(diǎn)。
同樣的前序、后序的下一個(gè)節(jié)點(diǎn)同理，舉一反三。
#include<bits/stdc++.h>
using namespace std;
struct node {//樹(shù)節(jié)點(diǎn)定義
int val;
node* left;//左子節(jié)點(diǎn)
node* right;//右子節(jié)點(diǎn)
node* parent;//父節(jié)點(diǎn)
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) {//有右子樹(shù)
node* r = p->right;//找最左
while (r->left != nullptr)
r = r->left;
next = r;
}
else if(p->parent!=nullptr){//無(wú)右子樹(shù)且有父節(jié)點(diǎn)
node* cur = p;
node* par = p->parent;
while (par != nullptr && cur == par->right) {
cur = par; //向上找到一個(gè)節(jié)點(diǎn)是它父節(jié)點(diǎn)的左節(jié)點(diǎn)
par = par->parent;
}
next = par;
}
return next;
}
int main() {
node* root = new node(1);//建樹(shù)
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("節(jié)點(diǎn)4的下一個(gè)節(jié)點(diǎn)：%d\n", test == nullptr ? -1 : test->val);
test = getnext(p5);
printf("節(jié)點(diǎn)5的下一個(gè)節(jié)點(diǎn)：%d\n", test == nullptr ? -1 : test->val);
test = getnext(p8);
printf("節(jié)點(diǎn)8的下一個(gè)節(jié)點(diǎn)：%d\n", test == nullptr ? -1 : test->val);
test = getnext(p6);
printf("節(jié)點(diǎn)6的下一個(gè)節(jié)點(diǎn)：%d\n", test == nullptr ? -1 : test->val);
return 0;
}
運(yùn)行結(jié)果如下：
節(jié)點(diǎn)4的下一個(gè)節(jié)點(diǎn)：8 節(jié)點(diǎn)5的下一個(gè)節(jié)點(diǎn)：3 節(jié)點(diǎn)8的下一個(gè)節(jié)點(diǎn)：1 節(jié)點(diǎn)6的下一個(gè)節(jié)點(diǎn)：-1
二叉搜索樹(shù)的后序遍歷路徑
題目：輸入一個(gè)整數(shù)數(shù)組，判斷該數(shù)組是不是某二叉搜索樹(shù)的后序遍歷結(jié)果。假設(shè)輸入的數(shù)組任意兩個(gè)數(shù)字不相同。
在后序遍歷中，最后一個(gè)節(jié)點(diǎn)是根節(jié)點(diǎn)，而且因?yàn)槭嵌嫠阉鳂?shù)，左子樹(shù)比它小，右子樹(shù)比它大，所以又可以劃分出左右子樹(shù)兩部分，然后在劃分出來(lái)的子樹(shù)中，同樣是最后一個(gè)是根節(jié)點(diǎn)，遞歸處理即可。
其實(shí)通過(guò)二叉搜索樹(shù)隱含條件來(lái)判斷，相當(dāng)于給一個(gè)二叉樹(shù)的后序和中序求是否能建樹(shù)，同前面重建二叉樹(shù)那題，換湯不換藥。
#include<bits/stdc++.h>
using namespace std;
struct node {//樹(shù)節(jié)點(diǎn)定義
int val;
node* left;//左子節(jié)點(diǎn)
node* right;//右子節(jié)點(diǎn)
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];//根節(jié)點(diǎn)
int i = 0;
while (i < len - 1) {//找左子樹(shù)中小于根節(jié)點(diǎn)的值
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)//驗(yàn)證左子樹(shù)
l = verify(s, i);
if (i < len - 1)//驗(yàn)證右子樹(shù)
r = verify(s + i, len - i - 1);
return (l && r);
}
int main() {
int a[10] = { 1,3,2,5,7,6,4 };
printf("數(shù)組a%s二叉搜索樹(shù)的后序序列\(zhòng)n", verify(a,7) ? "是" : "不是");
int b[10] = { 3,4,1,2 };
printf("數(shù)組b%s二叉搜索樹(shù)的后序序列\(zhòng)n", verify(b, 4) ? "是" : "不是");
return 0;
}
運(yùn)行結(jié)果如下：
數(shù)組a是二叉搜索樹(shù)的后序序列數(shù)組b不是二叉搜索樹(shù)的后序序列
二叉樹(shù)中和為某一值的路徑
題目：輸入一顆二叉樹(shù)和一個(gè)整數(shù)，打印出二叉樹(shù)中節(jié)點(diǎn)值的和為輸入整數(shù)的所有路徑。從樹(shù)的根節(jié)點(diǎn)開(kāi)始往下一直到葉節(jié)點(diǎn)所經(jīng)過(guò)的節(jié)點(diǎn)形成一條路徑。
首先由于路徑的定義是從根節(jié)點(diǎn)到葉節(jié)點(diǎn)，而只有前序遍歷中是先訪問(wèn)根節(jié)點(diǎn)的。當(dāng)前序遍歷訪問(wèn)到某一節(jié)點(diǎn)時(shí)，我們把該節(jié)點(diǎn)添加到路徑上，并累加該節(jié)點(diǎn)的值。如果節(jié)點(diǎn)是葉節(jié)點(diǎn)，此時(shí)判斷累加值是否符合輸入整數(shù)，符合則打印出路徑。當(dāng)訪問(wèn)結(jié)束后，要在路徑上刪除該節(jié)點(diǎn)，并減去該節(jié)點(diǎn)的值。即一個(gè)簡(jiǎn)單的dfs。
#include<bits/stdc++.h>
using namespace std;
struct node {//樹(shù)節(jié)點(diǎn)定義
int val;
node* left;//左子節(jié)點(diǎn)
node* right;//右子節(jié)點(diǎn)
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) {
//值相同且是葉節(jié)點(diǎn)
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;
}
運(yùn)行結(jié)果如下：
10 3 2 10 5
二叉搜索樹(shù)與雙向鏈表
題目：輸入一顆二叉搜索樹(shù)，將該二叉樹(shù)轉(zhuǎn)換成一個(gè)排序的雙向鏈表。要求不能創(chuàng)建任何新的節(jié)點(diǎn)，只能調(diào)整書(shū)中節(jié)點(diǎn)指針的指向。
二叉搜索樹(shù)的左節(jié)點(diǎn)小于父節(jié)點(diǎn)，右節(jié)點(diǎn)大于父節(jié)點(diǎn)，所以可以將原先指向左子節(jié)點(diǎn)的指針調(diào)整為列表中指向前一個(gè)節(jié)點(diǎn)的指針，原先指向右節(jié)點(diǎn)的指針調(diào)整為指向后一個(gè)節(jié)點(diǎn)的指針。
由于轉(zhuǎn)換后的鏈表是排好序的，所以我們可以中序遍歷樹(shù)的節(jié)點(diǎn)，當(dāng)遍歷到根節(jié)點(diǎn)是，可以把樹(shù)拆成三部分，4號(hào)節(jié)點(diǎn)、根節(jié)點(diǎn)為2的左子樹(shù)、根節(jié)點(diǎn)為6的右子樹(shù)。同時(shí)根據(jù)定義，將它與左子樹(shù)最大節(jié)點(diǎn)鏈接起來(lái)，與右子樹(shù)最小節(jié)點(diǎn)鏈接起來(lái)。而此時(shí)的左子樹(shù)儼然就是一個(gè)排序的鏈表，接著去遍歷右子樹(shù)即可，可不還是遞歸嗎。
#include<bits/stdc++.h>
using namespace std;
struct node {//樹(shù)節(jié)點(diǎn)定義
int val;
node* left;//左子節(jié)點(diǎn)
node* right;//右子節(jié)點(diǎn)
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;//根節(jié)點(diǎn)左指針指向左子樹(shù)最后一個(gè)節(jié)點(diǎn)
if (*t != nullptr)
(*t)->right = cur;//左子樹(shù)最后一個(gè)節(jié)點(diǎn)右指針指向根節(jié)點(diǎn)
*t = cur;//更新最后一個(gè)節(jié)點(diǎn)
if (cur->right != nullptr)
dfs(cur->right, t);
}
node* toList(node* root) {
node* tail = nullptr;//指向雙向鏈表尾節(jié)點(diǎn)
dfs(root, &tail);
node* head = tail; //頭節(jié)點(diǎn)
while (head != nullptr && head->left != nullptr)
head = head->left; //left指向前一個(gè)
return head;
}
int main() {
node* root = new node(4);//構(gòu)建一顆二叉搜索樹(shù)
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;
運(yùn)行結(jié)果：
1 2 3 4 5 6 7 7 6 5 4 3 2 1
總結(jié)
本篇文章就到這里了，希望能給你帶來(lái)幫助，也希望您能夠多多關(guān)注腳本之家的更多內(nèi)容!
相關(guān)文章
這篇文章主要為大家詳細(xì)介紹了SpringBoot讀取配置文件的五種方法，文中的示例代碼講解詳細(xì)，對(duì)我們學(xué)習(xí)SpringBoot有一定幫助，需要的可以參考一下2022-08-08
詳解java一維數(shù)組及練習(xí)題實(shí)例
在本篇文章里小編給大家整理了關(guān)于java一維數(shù)組及練習(xí)題的相關(guān)知識(shí)點(diǎn)和實(shí)例代碼，有需要的朋友們跟著學(xué)習(xí)下。2019-07-07
本篇文章是對(duì)final變量的初始化進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下2013-06-06
這篇文章主要介紹了Java基礎(chǔ)之文件概述,文中有非常詳細(xì)的代碼示例,對(duì)正在學(xué)習(xí)java基礎(chǔ)的小伙伴們有一定的幫助,需要的朋友可以參考下2021-05-05
Java日常練習(xí)題,每天進(jìn)步一點(diǎn)點(diǎn)(33)
下面小編就為大家?guī)?lái)一篇Java基礎(chǔ)的幾道練習(xí)題(分享)。小編覺(jué)得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧，希望可以幫到你2021-07-07
SpringBoot中集成企業(yè)微信機(jī)器人實(shí)現(xiàn)運(yùn)維報(bào)警的示例
本文主要介紹了SpringBoot中集成企業(yè)微信機(jī)器人實(shí)現(xiàn)運(yùn)維報(bào)警，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2022-05-05
這篇文章主要介紹了如何使用Java中的Optional，幫助大家更好的理解和使用Java，感興趣的朋友可以了解下2020-11-11
springboot項(xiàng)目使用Disruptor做內(nèi)部消息隊(duì)列的實(shí)現(xiàn)
本文主要介紹了springboot項(xiàng)目使用Disruptor做內(nèi)部消息隊(duì)列的實(shí)現(xiàn)，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2023-07-07
java代理模式（靜態(tài)代理、動(dòng)態(tài)代理、cglib代理）
代理(Proxy)是一種設(shè)計(jì)模式,提供了對(duì)目標(biāo)對(duì)象另外的訪問(wèn)方式;這篇文章主要介紹了Java 中的三種代理模式,需要的朋友可以參考下,希望能給你帶來(lái)幫助2021-07-07
Spring Security保護(hù)用戶密碼常用方法詳解
這篇文章主要介紹了Spring Security保護(hù)用戶密碼常用方法詳解,文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-09-09