二叉樹(shù)操作的相關(guān)知識(shí)和代碼詳解

樹(shù)是數(shù)據(jù)結(jié)構(gòu)中的重中之重，尤其以各類(lèi)二叉樹(shù)為學(xué)習(xí)的難點(diǎn)。在面試環(huán)節(jié)中，二叉樹(shù)也是必考的模塊。本文主要講二叉樹(shù)操作的相關(guān)知識(shí)，梳理面試?？嫉膬?nèi)容。請(qǐng)大家跟隨小編一起來(lái)復(fù)習(xí)吧。

本篇針對(duì)面試中常見(jiàn)的二叉樹(shù)操作作個(gè)總結(jié)：

前序遍歷，中序遍歷，后序遍歷；

層次遍歷；

求樹(shù)的結(jié)點(diǎn)數(shù)；

求樹(shù)的葉子數(shù)；

求樹(shù)的深度；

求二叉樹(shù)第k層的結(jié)點(diǎn)個(gè)數(shù)；

判斷兩棵二叉樹(shù)是否結(jié)構(gòu)相同；

求二叉樹(shù)的鏡像；

求兩個(gè)結(jié)點(diǎn)的最低公共祖先結(jié)點(diǎn)；

求任意兩結(jié)點(diǎn)距離；

找出二叉樹(shù)中某個(gè)結(jié)點(diǎn)的所有祖先結(jié)點(diǎn)；

不使用遞歸和棧遍歷二叉樹(shù)；

二叉樹(shù)前序中序推后序；

判斷二叉樹(shù)是不是完全二叉樹(shù)；

判斷是否是二叉查找樹(shù)的后序遍歷結(jié)果；

給定一個(gè)二叉查找樹(shù)中的結(jié)點(diǎn)，找出在中序遍歷下它的后繼和前驅(qū)；

二分查找樹(shù)轉(zhuǎn)化為排序的循環(huán)雙鏈表；

有序鏈表轉(zhuǎn)化為平衡的二分查找樹(shù)；

判斷是否是二叉查找樹(shù)。

1 前序遍歷，中序遍歷，后序遍歷；

1.1 前序遍歷

#FormatImgID_0#對(duì)于當(dāng)前結(jié)點(diǎn)，先輸出該結(jié)點(diǎn)，然后輸出它的左孩子，最后輸出它的右孩子。以上圖為例，遞歸的過(guò)程如下：

輸出 1，接著左孩子；

輸出 2，接著左孩子；

輸出 4，左孩子為空，再接著右孩子；

輸出 6，左孩子為空，再接著右孩子；

輸出 7，左右孩子都為空，此時(shí) 2 的左子樹(shù)全部輸出，2 的右子樹(shù)為空，此時(shí) 1 的左子樹(shù)全部輸出，接著 1 的右子樹(shù)；

輸出 3，接著左孩子；

輸出 5，左右孩子為空，此時(shí) 3 的左子樹(shù)全部輸出，3 的右子樹(shù)為空，至此 1 的右子樹(shù)全部輸出，結(jié)束。

而非遞歸版本只是利用 stack 模擬上述過(guò)程而已，遞歸的過(guò)程也就是出入棧的過(guò)程。

/*前序遍歷遞歸版*/

voidPreOrderRec(Node*node)

{

if(node==nullptr)

return;

cout<data<

PreOrderRec(node->left);//然后輸出左孩子

PreOrderRec(node->right);//最后輸出右孩子

}

/*前序遍歷非遞歸版*/

voidPreOrderNonRec(Node*node)

{

if(node==nullptr)

return;

stackS;

cout<data<

S.push(node);

node=node->left;

while(!S.empty()||node)

{

while(node)

{

cout<data<

S.push(node);

node=node->left;//然后輸出左孩子

}//while結(jié)束意味著左孩子已經(jīng)全部輸出

node=S.top()->right;//最后輸出右孩子

S.pop();

}

}

1.2 中序遍歷

對(duì)于當(dāng)前結(jié)點(diǎn)，先輸出它的左孩子，然后輸出該結(jié)點(diǎn)，最后輸出它的右孩子。以（1.1）圖為例：

1-->2-->4，4 的左孩子為空，輸出 4，接著右孩子；

6 的左孩子為空，輸出 6，接著右孩子；

7 的左孩子為空，輸出 7，右孩子也為空，此時(shí) 2 的左子樹(shù)全部輸出，輸出 2，2 的右孩子為空，此時(shí) 1 的左子樹(shù)全部輸出，輸出 1，接著 1 的右孩子；

3-->5，5 左孩子為空，輸出 5，右孩子也為空，此時(shí) 3 的左子樹(shù)全部輸出，而 3 的右孩子為空，至此 1 的右子樹(shù)全部輸出，結(jié)束。

/*中序遍歷遞歸版*/

voidInOrderRec(Node*node)

{

if(node==nullptr)

return;

InOrderRec(node->left);//先輸出左孩子

cout<data<

InOrderRec(node->right);//最后輸出右孩子

}

/*前序遍歷非遞歸版*/

voidInOrderNonRec(Node*node)

{

if(node==nullptr)

return;

stackS;

S.push(node);

node=node->left;

while(!S.empty()||node)

{

while(node)

{

S.push(node);

node=node->left;

}//while結(jié)束意味著左孩子為空

cout<data<

node=S.top()->right;//左孩子全部輸出，當(dāng)前結(jié)點(diǎn)也輸出后，最后輸出右孩子

S.pop();

}

}

1.3 后序遍歷

對(duì)于當(dāng)前結(jié)點(diǎn)，先輸出它的左孩子，然后輸出它的右孩子，最后輸出該結(jié)點(diǎn)。依舊以（1.1）圖為例：

1->2->4->6->7，7 無(wú)左孩子，也無(wú)右孩子，輸出 7，此時(shí) 6 無(wú)左孩子，而 6 的右子樹(shù)也全部輸出，輸出 6，此時(shí) 4 無(wú)左子樹(shù)，而 4 的右子樹(shù)已全部輸出，接著輸出 4，此時(shí) 2 的左子樹(shù)全部輸出，且 2 無(wú)右子樹(shù)，輸出 2，此時(shí) 1 的左子樹(shù)全部輸出，接著轉(zhuǎn)向右子樹(shù)；

3->5，5 無(wú)左孩子，也無(wú)右孩子，輸出 5，此時(shí) 3 的左子樹(shù)全部輸出，且 3 無(wú)右孩子，輸出 3，此時(shí) 1 的右子樹(shù)全部輸出，輸出 1，結(jié)束。

非遞歸版本中，對(duì)于一個(gè)結(jié)點(diǎn)，如果我們要輸出它，只有它既沒(méi)有左孩子也沒(méi)有右孩子或者它有孩子但是它的孩子已經(jīng)被輸出（由此設(shè)置 pre 變量）。若非上述兩種情況，則將該結(jié)點(diǎn)的右孩子和左孩子依次入棧，這樣就保證了每次取棧頂元素的時(shí)候,先依次遍歷左子樹(shù)和右子樹(shù)。

/*后序遍歷遞歸版*/

voidPostOrderRec(Node*node)

{

if(node==nullptr)

return;

PostOrderRec(node->left);//先輸出左孩子

PostOrderRec(node->right);//然后輸出右孩子

cout<data<

}

/*后序遍歷非遞歸版*/

voidPostOrderNonRec(Node*node)

{

if(node==nullptr)

return;

Node*pre=nullptr;

stackS;

S.push(node);

while(!S.empty())

{

node=S.top();

if((!node->left&&!node->right)||//第一個(gè)輸出的必是無(wú)左右孩子的葉子結(jié)點(diǎn)，只要第一個(gè)結(jié)點(diǎn)輸出，

(pre &&(pre == node->left || pre == node->right)))//以后的 pre 就不會(huì)是空。此處的判斷語(yǔ)句加入一個(gè) pre，只是用來(lái)

{//確?？梢哉_輸出第一個(gè)結(jié)點(diǎn)。

cout<data<

pre=node;

S.pop();

}

else

{

if(node->right)

S.push(node->right);//先進(jìn)右孩子，再進(jìn)左孩子，取出來(lái)的才是左孩子

if(node->left)

S.push(node->left);

}

}

}

2 層次遍歷

voidLevelOrder(Node*node)

{

Node*p=node;

queueQ;//隊(duì)列

Q.push(p);

while(!Q.empty())

{

p=Q.front();

cout<data<

Q.pop();

if(p->left)

Q.push(p->left);//注意順序，先進(jìn)左孩子

if(p->right)

Q.push(p->right);

}

}

3 求樹(shù)的結(jié)點(diǎn)數(shù)

intCountNodes(Node*node)

{

if(node==nullptr)

return0;

returnCountNodes(node->left)+CountNodes(node->right)+1;

}

4 求樹(shù)的葉子數(shù)

intCountLeaves(Node*node)

{

if(node==nullptr)

return0;

if(!node->left&&!node->right)

return1;

returnCountLeaves(node->left)+CountLeaves(node->right);

}

5 求樹(shù)的深度

intGetDepth(Node*node)

{

if(node==nullptr)

return0;

intleft_depth=GetDepth(node->left)+1;

intright_depth=GetDepth(node->right)+1;

returnleft_depth>right_depth?left_depth:right_depth;

}

6 求二叉樹(shù)第k層的結(jié)點(diǎn)個(gè)數(shù)

intGetKLevel(Node*node,intk)

{

if(node==nullptr)

return0;

if(k==1)

return1;

returnGetKLevel(node->left,k-1)+GetKLevel(node->right,k-1);

}

7 判斷兩棵二叉樹(shù)是否結(jié)構(gòu)相同

不考慮數(shù)據(jù)內(nèi)容。結(jié)構(gòu)相同意味著對(duì)應(yīng)的左子樹(shù)和對(duì)應(yīng)的右子樹(shù)都結(jié)構(gòu)相同。

boolStructureCmp(Node*node1,Node*node2)

{

if(node1==nullptr&&node2==nullptr)

returntrue;

elseif(node1==nullptr||node2==nullptr)

returnfalse;

returnStructureCmp(node1->left,node2->left)&&Str1uctureCmp(node1->right,node2->right);

}

8 求二叉樹(shù)的鏡像

對(duì)于每個(gè)結(jié)點(diǎn)，我們交換它的左右孩子即可。

voidMirror(Node*node)

{

if(node==nullptr)

return;

Node*temp=node->left;

node->left=node->right;

node->right=temp;

Mirror(node->left);

Mirror(node->right);

}

9 求兩個(gè)結(jié)點(diǎn)的最低公共祖先結(jié)點(diǎn)

最低公共祖先，即 LCA（Lowest Common Ancestor），見(jiàn)下圖：#FormatImgID_1#結(jié)點(diǎn) 3 和結(jié)點(diǎn) 4 的最近公共祖先是結(jié)點(diǎn) 2，即 LCA(3,4)=2。在此，需要注意到當(dāng)兩個(gè)結(jié)點(diǎn)在同一棵子樹(shù)上的情況，如結(jié)點(diǎn) 3 和結(jié)點(diǎn) 2 的最近公共祖先為 2，即 LCA(3,2)=2。同理 LCA(5,6)=4，LCA(6,10)=1。

Node*FindLCA(Node*node,Node*target1,Node*target2)

{

if(node==nullptr)

returnnullptr;

if(node==target1||node==target2)

returnnode;

Node*left=FindLCA(node->left,target1,target2);

Node*right=FindLCA(node->right,target1,target2);

if(left&&right)//分別在左右子樹(shù)

returnnode;

returnleft?left:right;//都在左子樹(shù)或右子樹(shù)

}

10 求任意兩結(jié)點(diǎn)距離

#FormatImgID_2#首先找到兩個(gè)結(jié)點(diǎn)的 LCA，然后分別計(jì)算 LCA 與它們的距離，最后相加即可。

intFindLevel(Node*node,Node*target)

{

if(node==nullptr)

return-1;

if(node==target)

return0;

intlevel=FindLevel(node->left,target);//先在左子樹(shù)找

if(level==-1)

level=FindLevel(node->right,target);//如果左子樹(shù)沒(méi)找到，在右子樹(shù)找

if(level!=-1)//找到了，回溯

returnlevel+1;

return-1;//如果左右子樹(shù)都沒(méi)找到

}

intDistanceNodes(Node*node,Node*target1,Node*target2)

{

Node*lca=FindLCA(node,target1,target2);//找到最低公共祖先結(jié)點(diǎn)

intlevel1=FindLevel(lca,target1);

intlevel2=FindLevel(lca,target2);

returnlevel1+level2;

}

11 找出二叉樹(shù)中某個(gè)結(jié)點(diǎn)的所有祖先結(jié)點(diǎn)

#FormatImgID_3#如果給定結(jié)點(diǎn) 5，則其所有祖先結(jié)點(diǎn)為 4,2,1。

boolFindAllAncestors(Node*node,Node*target)

{

if(node==nullptr)

returnfalse;

if(node==target)

returntrue;

if(FindAllAncestors(node->left,target)||FindAllAncestors(node->right,target))//找到了

{

cout<data<

returntrue;//回溯

}

returnfalse;//如果左右子樹(shù)都沒(méi)找到

}

12 不使用遞歸和棧遍歷二叉樹(shù)

1968 年，高德納（Donald Knuth）提出一個(gè)問(wèn)題：是否存在一個(gè)算法，它不使用棧也不破壞二叉樹(shù)結(jié)構(gòu)，但是可以完成對(duì)二叉樹(shù)的遍歷？隨后 1979 年，James H. Morris 提出了二叉樹(shù)線索化，解決了這個(gè)問(wèn)題。（根據(jù)這個(gè)概念我們又提出了一個(gè)新的數(shù)據(jù)結(jié)構(gòu)，即線索二叉樹(shù)，因線索二叉樹(shù)不是本文要介紹的內(nèi)容，所以有興趣的朋友請(qǐng)移步線索二叉樹(shù)）

前序，中序，后序遍歷，不管是遞歸版本還是非遞歸版本，都用到了一個(gè)數(shù)據(jù)結(jié)構(gòu)--棧，為何要用棧？那是因?yàn)槠渌姆绞經(jīng)]法記錄當(dāng)前結(jié)點(diǎn)的 parent,而如果在每個(gè)結(jié)點(diǎn)的結(jié)構(gòu)里面加個(gè) parent 分量顯然是不現(xiàn)實(shí)的，而線索化正好解決了這個(gè)問(wèn)題，其含義就是利用結(jié)點(diǎn)的右孩子空指針，指向該結(jié)點(diǎn)在中序序列中的后繼。下面具體來(lái)看看如何使用線索化來(lái)完成對(duì)二叉樹(shù)的遍歷。#FormatImgID_4#先看前序遍歷，步驟如下：

如果當(dāng)前結(jié)點(diǎn)的左孩子為空，則輸出當(dāng)前結(jié)點(diǎn)并將其右孩子作為當(dāng)前結(jié)點(diǎn)；

如果當(dāng)前結(jié)點(diǎn)的左孩子不為空，在當(dāng)前結(jié)點(diǎn)的左子樹(shù)中找到當(dāng)前結(jié)點(diǎn)在中序遍歷下的前驅(qū)結(jié)點(diǎn)；

2.1如果前驅(qū)結(jié)點(diǎn)的右孩子為空，將它的右孩子設(shè)置為當(dāng)前結(jié)點(diǎn)，輸出當(dāng)前結(jié)點(diǎn)并把當(dāng)前結(jié)點(diǎn)更新為當(dāng)前結(jié)點(diǎn)的左孩子；

2.2如果前驅(qū)結(jié)點(diǎn)的右孩子為當(dāng)前結(jié)點(diǎn)，將它的右孩子重新設(shè)為空，當(dāng)前結(jié)點(diǎn)更新為當(dāng)前結(jié)點(diǎn)的右孩子；

重復(fù)以上步驟 1 和 2，直到當(dāng)前結(jié)點(diǎn)為空。

/*前序遍歷*/

voidPreOrderMorris(Node*root)

{

Node*cur=root;

Node*pre=nullptr;

while(cur)

{

if(cur->left==nullptr)//步驟1

{

cout<data<

cur=cur->right;

}

else

{

pre=cur->left;

while(pre->right&&pre->right!=cur)//步驟2，找到cur的前驅(qū)結(jié)點(diǎn)

pre=pre->right;

if(pre->right==nullptr)//步驟2.1，cur未被訪問(wèn)，將cur結(jié)點(diǎn)作為其前驅(qū)結(jié)點(diǎn)的右孩子

{

cout<data<

pre->right=cur;

cur=cur->left;

}

else//步驟2.2，cur已被訪問(wèn)，恢復(fù)樹(shù)的原有結(jié)構(gòu)，更改right指針

{

pre->right=nullptr;

cur=cur->right;

}

}

}

}

再來(lái)看中序遍歷，和前序遍歷相比只改動(dòng)一句代碼，步驟如下：

如果當(dāng)前結(jié)點(diǎn)的左孩子為空，則輸出當(dāng)前結(jié)點(diǎn)并將其右孩子作為當(dāng)前結(jié)點(diǎn)；

如果當(dāng)前結(jié)點(diǎn)的左孩子不為空，在當(dāng)前結(jié)點(diǎn)的左子樹(shù)中找到當(dāng)前結(jié)點(diǎn)在中序遍歷下的前驅(qū)結(jié)點(diǎn)；

2.1. 如果前驅(qū)結(jié)點(diǎn)的右孩子為空，將它的右孩子設(shè)置為當(dāng)前結(jié)點(diǎn)，當(dāng)前結(jié)點(diǎn)更新為當(dāng)前結(jié)點(diǎn)的左孩子；

2.2. 如果前驅(qū)結(jié)點(diǎn)的右孩子為當(dāng)前結(jié)點(diǎn)，將它的右孩子重新設(shè)為空，輸出當(dāng)前結(jié)點(diǎn)，當(dāng)前結(jié)點(diǎn)更新為當(dāng)前結(jié)點(diǎn)的右孩子；

重復(fù)以上步驟 1 和 2，直到當(dāng)前結(jié)點(diǎn)為空。

/*中序遍歷*/

voidInOrderMorris(Node*root)

{

Node*cur=root;

Node*pre=nullptr;

while(cur)

{

if(cur->left==nullptr)//（1）

{

cout<data<

cur=cur->right;

}

else

{

pre=cur->left;

while(pre->right&&pre->right!=cur)//（2），找到cur的前驅(qū)結(jié)點(diǎn)

pre=pre->right;

if(pre->right==nullptr)//（2.1），cur未被訪問(wèn)，將cur結(jié)點(diǎn)作為其前驅(qū)結(jié)點(diǎn)的右孩子

{

pre->right=cur;

cur=cur->left;

}

else//（2.2），cur已被訪問(wèn)，恢復(fù)樹(shù)的原有結(jié)構(gòu)，更改right指針

{

cout<data<

pre->right=nullptr;

cur=cur->right;

}

}

}

}

最后看下后序遍歷，后序遍歷有點(diǎn)復(fù)雜，需要建立一個(gè)虛假根結(jié)點(diǎn) dummy，令其左孩子是 root。并且還需要一個(gè)子過(guò)程，就是倒序輸出某兩個(gè)結(jié)點(diǎn)之間路徑上的各個(gè)結(jié)點(diǎn)。#FormatImgID_5#步驟如下：

如果當(dāng)前結(jié)點(diǎn)的左孩子為空，則將其右孩子作為當(dāng)前結(jié)點(diǎn)；

如果當(dāng)前結(jié)點(diǎn)的左孩子不為空，在當(dāng)前結(jié)點(diǎn)的左子樹(shù)中找到當(dāng)前結(jié)點(diǎn)在中序遍歷下的前驅(qū)結(jié)點(diǎn)；

2.1. 如果前驅(qū)結(jié)點(diǎn)的右孩子為空，將它的右孩子設(shè)置為當(dāng)前結(jié)點(diǎn)，當(dāng)前結(jié)點(diǎn)更新為當(dāng)前結(jié)點(diǎn)的左孩子；

2.2. 如果前驅(qū)結(jié)點(diǎn)的右孩子為當(dāng)前結(jié)點(diǎn)，將它的右孩子重新設(shè)為空，倒序輸出從當(dāng)前結(jié)點(diǎn)的左孩子到該前驅(qū)結(jié)點(diǎn)這條路徑上的所有結(jié)點(diǎn)，當(dāng)前結(jié)點(diǎn)更新為當(dāng)前結(jié)點(diǎn)的右孩子；

重復(fù)以上步驟 1 和 2，直到當(dāng)前結(jié)點(diǎn)為空。

structNode

{

intdata;

Node*left;

Node*right;

Node(intdata_,Node*left_,Node*right_)

{

data=data_;

left=left_;

right=right_;

}

};

voidReversePrint(Node*from,Node*to)

{

if(from==to)

{

cout<data<

return;

}

ReversePrint(from->right,to);

cout<data<

}

voidPostOrderMorris(Node*root)

{

Node*dummy=newNode(-1,root,nullptr);//一個(gè)虛假根結(jié)點(diǎn)

Node*cur=dummy;

Node*pre=nullptr;

while(cur)

{

if(cur->left==nullptr)//步驟1

cur=cur->right;

else

{

pre=cur->left;

while(pre->right&&pre->right!=cur)//步驟2，找到cur的前驅(qū)結(jié)點(diǎn)

pre=pre->right;

if(pre->right==nullptr)//步驟2.1，cur未被訪問(wèn)，將cur結(jié)點(diǎn)作為其前驅(qū)結(jié)點(diǎn)的右孩子

{

pre->right=cur;

cur=cur->left;

}

else//步驟2.2，cur已被訪問(wèn)，恢復(fù)樹(shù)的原有結(jié)構(gòu)，更改right指針

{

pre->right=nullptr;

ReversePrint(cur->left,pre);

cur=cur->right;

}

}

}

}

dummy 用的非常巧妙，建議讀者配合上面的圖模擬下算法流程。

13 二叉樹(shù)前序中序推后序

方式	序列
前序	[1 2 4 7 3 5 8 9 6]
中序	[4 7 2 1 8 5 9 3 6]
后序	[7 4 2 8 9 5 6 3 1]

以上面圖表為例，步驟如下：

根據(jù)前序可知根結(jié)點(diǎn)為1；

根據(jù)中序可知 4 7 2 為根結(jié)點(diǎn) 1 的左子樹(shù)和 8 5 9 3 6 為根結(jié)點(diǎn) 1 的右子樹(shù)；

遞歸實(shí)現(xiàn)，把 4 7 2 當(dāng)做新的一棵樹(shù)和 8 5 9 3 6 也當(dāng)做新的一棵樹(shù)；

在遞歸的過(guò)程中輸出后序。

/*前序遍歷和中序遍歷結(jié)果以長(zhǎng)度為n的數(shù)組存儲(chǔ)，pos1為前序數(shù)組下標(biāo)，pos2為后序下標(biāo)*/

intpre_order_arry[n];

intin_order_arry[n];

voidPrintPostOrder(intpos1,intpos2,intn)

{

if(n==1)

{

cout<

return;

}

if(n==0)

return;

inti=0;

for(;pre_order_arry[pos1]!=in_order_arry[pos2+i];i++)

;

PrintPostOrder(pos1+1,pos2,i);

PrintPostOrder(pos1+i+1,pos2+i+1,n-i-1);

cout<

}

當(dāng)然我們也可以根據(jù)前序和中序構(gòu)造出二叉樹(shù)，進(jìn)而求出后序。

/*該函數(shù)返回二叉樹(shù)的根結(jié)點(diǎn)*/

Node*Create(intpos1,intpos2,intn)

{

Node*p=nullptr;

for(inti=0;i

{

if(pre_order_arry[pos1]==in_order_arry[pos2+i])

{

p=newNode(pre_order_arry[pos1]);

p->left=Create(pos1+1,pos2,i);

p->right=Create(pos1+i+1,pos2+i+1,n-i-1);

returnp;

}

}

returnp;

}

14 判斷二叉樹(shù)是不是完全二叉樹(shù)

若設(shè)二叉樹(shù)的深度為 h，除第 h 層外，其它各層 (1～h-1) 的結(jié)點(diǎn)數(shù)都達(dá)到最大個(gè)數(shù)，第 h 層所有的結(jié)點(diǎn)都連續(xù)集中在最左邊，這就是完全二叉樹(shù)（Complete Binary Tree）。如下圖：#FormatImgID_6#

首先若一個(gè)結(jié)點(diǎn)只有右孩子，肯定不是完全二叉樹(shù)；其次若只有左孩子或沒(méi)有孩子，那么接下來(lái)的所有結(jié)點(diǎn)肯定都沒(méi)有孩子，否則就不是完全二叉樹(shù)，因此設(shè)置 flag 標(biāo)記變量。

boolIsCBT(Node*node)

{

boolflag=false;

queueQ;

Q.push(node);

while(!Q.empty())

{

Node*p=Q.front();

Q.pop();

if(flag)

{

if(p->left||p->right)

returnfalse;

}

else

{

if(p->left&&p->right)

{

Q.push(p->left);

Q.push(p->right);

}

elseif(p->right)//只有右結(jié)點(diǎn)

returnfalse;

elseif(p->left)//只有左結(jié)點(diǎn)

{

Q.push(p->left);

flag=true;

}

else//沒(méi)有結(jié)點(diǎn)

flag=true;

}

}

returntrue;

}

15 判斷是否是二叉查找樹(shù)的后序遍歷結(jié)果

在后續(xù)遍歷得到的序列中，最后一個(gè)元素為樹(shù)的根結(jié)點(diǎn)。從頭開(kāi)始掃描這個(gè)序列，比根結(jié)點(diǎn)小的元素都應(yīng)該位于序列的左半部分；從第一個(gè)大于跟結(jié)點(diǎn)開(kāi)始到跟結(jié)點(diǎn)前面的一個(gè)元素為止，所有元素都應(yīng)該大于跟結(jié)點(diǎn)，因?yàn)檫@部分元素對(duì)應(yīng)的是樹(shù)的右子樹(shù)。根據(jù)這樣的劃分，把序列劃分為左右兩部分，我們遞歸地確認(rèn)序列的左、右兩部分是不是都是二元查找樹(shù)。

intarray[n];//長(zhǎng)度為n的序列，注意begin和end遵循的是左閉右閉原則

boolIsSequenceOfBST(intbegin,intend)

{

if(end-begin<=?0)

returntrue;

introot_data=array[end];//數(shù)組尾元素為根結(jié)點(diǎn)

inti=begin;

for(;array[i]

;

intj=i;

for(;j

if(array[j]< root_data)??//?此時(shí)右子樹(shù)應(yīng)該都大于根結(jié)點(diǎn)；若存在小于，直接?return?false

returnfalse;

returnIsSequenceOfBST(begin,i-1)&&IsSequenceOfBST(i,end-1);//左右子樹(shù)是否都滿(mǎn)足

}

16 給定一個(gè)二叉查找樹(shù)中的結(jié)點(diǎn)（存在一個(gè)指向父親結(jié)點(diǎn)的指針），找出在中序遍歷下它的后繼和前驅(qū)

一棵二叉查找樹(shù)的中序遍歷序列，正好是升序序列。假如根結(jié)點(diǎn)的父結(jié)點(diǎn)為 nullptr，則：

如果當(dāng)前結(jié)點(diǎn)有右孩子，則后繼結(jié)點(diǎn)為這個(gè)右孩子的最左孩子；

如果當(dāng)前結(jié)點(diǎn)沒(méi)有右孩子；

2.1. 當(dāng)前結(jié)點(diǎn)為根結(jié)點(diǎn)，返回 nullptr；

2.2. 當(dāng)前結(jié)點(diǎn)只是個(gè)普通結(jié)點(diǎn)，也就是存在父結(jié)點(diǎn)；

2.2.1. 當(dāng)前結(jié)點(diǎn)是父親結(jié)點(diǎn)的左孩子，則父親結(jié)點(diǎn)就是后繼結(jié)點(diǎn)；

2.2.2. 當(dāng)前結(jié)點(diǎn)是父親結(jié)點(diǎn)的右孩子，沿著父親結(jié)點(diǎn)往上走，直到 n-1 代祖先是 n 代祖先的左孩子，則后繼為 n 代祖先或遍歷到根結(jié)點(diǎn)也沒(méi)找到符合的，則當(dāng)前結(jié)點(diǎn)就是中序遍歷的最后一個(gè)結(jié)點(diǎn)，返回 nullptr。

/*求后繼結(jié)點(diǎn)*/

Node*Increment(Node*node)

{

if(node->right)//步驟1

{

node=node->right;

while(node->left)

node=node->left;

returnnode;

}

else//步驟2

{

if(node->parent==nullptr)//步驟2.1

returnnullptr;

Node*p=node->parent;//步驟2.2

if(p->left==node)//步驟2.2.1

returnp;

else//步驟2.2.2

{

while(p->right==node)

{

node=p;

p=p->parent;

if(p==nullptr)

returnnullptr;

}

returnp;

}

}

}

仔細(xì)觀察上述代碼，總覺(jué)得有點(diǎn)啰嗦。比如，過(guò)多的 return，步驟 2 的層次太多。綜合考慮所有情況，改進(jìn)代碼如下：

Node*Increment(Node*node)

{

if(node->right)

{

node=node->right;

while(node->left)

node=node->left;

}

else

{

Node*p=node->parent;

while(p&&p->right==node)

{

node=p;

p=p->parent;

}

node=p;

}

returnnode;

}

上述的代碼是基于結(jié)點(diǎn)有 parent 指針的，若題意要求沒(méi)有 parent 呢？網(wǎng)上也有人給出了答案，個(gè)人覺(jué)得沒(méi)有什么價(jià)值，有興趣的朋友可以到這里查看。

而求前驅(qū)結(jié)點(diǎn)的話(huà)，只需把上述代碼的 left 與 right 互調(diào)即可，很簡(jiǎn)單。

17 二分查找樹(shù)轉(zhuǎn)化為排序的循環(huán)雙鏈表

二分查找樹(shù)的中序遍歷即為升序排列，問(wèn)題就在于如何在遍歷的時(shí)候更改指針的指向。一種簡(jiǎn)單的方法時(shí)，遍歷二分查找樹(shù)，將遍歷的結(jié)果放在一個(gè)數(shù)組中，之后再把該數(shù)組轉(zhuǎn)化為雙鏈表。如果題目要求只能使用 O(1)O(1) 內(nèi)存，則只能在遍歷的同時(shí)構(gòu)建雙鏈表，即進(jìn)行指針的替換。

我們需要用遞歸的方法來(lái)解決，假定每個(gè)遞歸調(diào)用都會(huì)返回構(gòu)建好的雙鏈表，可把問(wèn)題分解為左右兩個(gè)子樹(shù)。由于左右子樹(shù)都已經(jīng)是有序的，當(dāng)前結(jié)點(diǎn)作為中間的一個(gè)結(jié)點(diǎn)，把左右子樹(shù)得到的鏈表連接起來(lái)即可。

/*合并兩個(gè)a,b兩個(gè)循環(huán)雙向鏈表*/

Node*Append(Node*a,Node*b)

{

if(a==nullptr)returnb;

if(b==nullptr)returna;

//分別得到兩個(gè)鏈表的最后一個(gè)元素

Node*a_last=a->left;

Node*b_last=b->left;

//將兩個(gè)鏈表頭尾相連

a_last->right=b;

b->left=a_last;

a->left=b_last;

b_last->right=a;

returna;

}

/*遞歸的解決二叉樹(shù)轉(zhuǎn)換為雙鏈表*/

Node*TreeToList(Node*node)

{

if(node==nullptr)returnnullptr;

//遞歸解決子樹(shù)

Node*left_list=TreeToList(node->left);

Node*right_list=TreeToList(node->right);

//把根結(jié)點(diǎn)轉(zhuǎn)換為一個(gè)結(jié)點(diǎn)的雙鏈表，方便后面的鏈表合并

node->left=node;

node->right=node;

//合并之后即為升序排列

left_list=Append(left_list,node);

left_list=Append(left_list,right_list);

returnleft_list;

}

18 有序鏈表轉(zhuǎn)化為平衡的二分查找樹(shù)（Binary Search Tree）

我們可以采用自頂向下的方法。先找到中間結(jié)點(diǎn)作為根結(jié)點(diǎn)，然后遞歸左右兩部分。所以我們需要先找到中間結(jié)點(diǎn)，對(duì)于單鏈表來(lái)說(shuō)，必須要遍歷一邊，可以使用快慢指針加快查找速度。

structTreeNode

{

intdata;

TreeNode*left;

TreeNode*right;

TreeNode(intdata_){data=data_;left=right=nullptr;}

};

structListNode

{

intdata;

ListNode*next;

ListNode(intdata_){data=data_;next=nullptr;}

};

TreeNode*SortedListToBST(ListNode*list_node)

{

if(!list_node)returnnullptr;

if(!list_node->next)return(newTreeNode(list_node->data));

//用快慢指針找到中間結(jié)點(diǎn)

ListNode*pre_slow=nullptr;//記錄慢指針的前一個(gè)結(jié)點(diǎn)

ListNode*slow=list_node;//慢指針

ListNode*fast=list_node;//快指針

while(fast&&fast->next)

{

pre_slow=slow;

slow=slow->next;

fast=fast->next->next;

}

TreeNode*mid=newTreeNode(slow->data);

//分別遞歸左右兩部分

if(pre_slow)

{

pre_slow->next=nullptr;

mid->left=SortedListToBST(list_node);

}

mid->right=SortedListToBST(slow->next);

returnmid;

}

由 f(n)=2f(\frac n2)+\frac n2f(n)=2f(2n)+2n 得，所以上述算法的時(shí)間復(fù)雜度為 O(nlogn)O(nlogn)。

不妨換個(gè)思路，采用自底向上的方法：

TreeNode*SortedListToBSTRec(ListNode*&list,intstart,intend)

{

if(start>end)returnnullptr;

intmid=start+(end-start)/2;

TreeNode*left_child=SortedListToBSTRec(list,start,mid-1);//注意此處傳入的是引用

TreeNode*parent=newTreeNode(list->data);

parent->left=left_child;

list=list->next;

parent->right=SortedListToBSTRec(list,mid+1,end);

returnparent;

}

TreeNode*SortedListToBST(ListNode*node)

{

intn=0;

ListNode*p=node;

while(p)

{

n++;

p=p->next;

}

returnSortedListToBSTRec(node,0,n-1);

}

如此，時(shí)間復(fù)雜度降為 O(n)O(n)。

19 判斷是否是二叉查找樹(shù)

我們假定二叉樹(shù)沒(méi)有重復(fù)元素，即對(duì)于每個(gè)結(jié)點(diǎn)，其左右孩子都是嚴(yán)格的小于和大于。

下面給出兩個(gè)方法：

方法 1：

boolIsBST(Node*node,intmin,intmax)

{

if(node==nullptr)

returntrue;

if(node->data<=?min?||?node->data>=max)

returnfalse;

returnIsBST(node->left,min,node->data)&&IsBST(node->right,node->data,max);

}

IsBST(node,INT_MIN,INT_MAX);

方法 2：

利用二叉查找樹(shù)中序遍歷時(shí)元素遞增來(lái)判斷。

boolIsBST(Node*node)

{

staticintpre=INT_MIN;

if(node==nullptr)

returntrue;

if(!IsBST(node->left))

returnfalse;

if(node->data

returnfalse;

pre=node->data;

returnIsBST(node->right);

}