電子發(fā)燒友App
在數(shù)據(jù)結(jié)構(gòu)面試環(huán)節(jié)中，二叉樹(shù)是必考的模塊。本文主要講二叉樹(shù)操作的相關(guān)知識(shí)，梳理面試?？嫉膬?nèi)容。一起來(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 前序遍歷
對(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ò)程。
?
/* 前序遍歷遞歸版 */
void PreOrderRec(Node * node)
{
if (node == nullptr)
return;
cout << node->data << " "; // 先輸出當(dāng)前結(jié)點(diǎn)
PreOrderRec(node->left); // 然后輸出左孩子
PreOrderRec(node->right); // 最后輸出右孩子
}
/* 前序遍歷非遞歸版 */
void PreOrderNonRec(Node * node)
{
if (node == nullptr)
return;
stack S;
cout << node->data << " ";
S.push(node);
node = node->left;
while (!S.empty() || node)
{
while (node)
{
cout << node->data << " "; // 先輸出當(dāng)前結(jié)點(diǎn)
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é)束。
/* 中序遍歷遞歸版 */
void InOrderRec(Node * node)
{
if (node == nullptr)
return;
InOrderRec(node->left); // 先輸出左孩子
cout << node->data << " "; // 然后輸出當(dāng)前結(jié)點(diǎn)
InOrderRec(node->right); // 最后輸出右孩子
}
/* 前序遍歷非遞歸版 */
void InOrderNonRec(Node * node)
{
if (node == nullptr)
return;
stack S;
S.push(node);
node = node->left;
while (!S.empty() || node)
{
while (node)
{
S.push(node);
node = node->left;
} // while 結(jié)束意味著左孩子為空
cout << S.top()->data << " "; // 左孩子已經(jīng)全部輸出，接著輸出當(dāng)前結(jié)點(diǎn)
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ù)。
?
/* 后序遍歷遞歸版 */
void PostOrderRec(Node * node)
{
if (node == nullptr)
return;
PostOrderRec(node->left); // 先輸出左孩子
PostOrderRec(node->right); // 然后輸出右孩子
cout << node->data << " "; // 最后輸出當(dāng)前結(jié)點(diǎn)
}
/* 后序遍歷非遞歸版 */
void PostOrderNonRec(Node * node)
{
if (node == nullptr)
return;
Node * pre = nullptr;
stack S;
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 << node->data << " "; // 左右孩子都全部輸出，再輸出當(dāng)前結(jié)點(diǎn)
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 層次遍歷
void LevelOrder(Node * node)
{
Node * p = node;
queue Q; // 隊(duì)列
Q.push(p);
while (!Q.empty())
{
p = Q.front();
cout << p->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ù)
int CountNodes(Node * node)
{
if (node == nullptr)
return 0;
return CountNodes(node->left) + CountNodes(node->right) + 1;
}
?4 求樹(shù)的葉子數(shù)
int CountLeaves(Node * node)
{
if (node == nullptr)
return 0;
if (!node->left && !node->right)
return 1;
return CountLeaves(node->left) + CountLeaves(node->right);
}
?5 求樹(shù)的深度
int GetDepth(Node * node)
{
if (node == nullptr)
return 0;
int left_depth = GetDepth(node->left) + 1;
int right_depth = GetDepth(node->right) + 1;
return left_depth > right_depth ? left_depth : right_depth;
}
?
?
?
6 求二叉樹(shù)第k層的結(jié)點(diǎn)個(gè)數(shù)
int GetKLevel(Node * node, int k)
{
if (node == nullptr)
return 0;
if (k == 1)
return 1;
return GetKLevel(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)相同。
bool StructureCmp(Node * node1, Node * node2)
{
if (node1 == nullptr && node2 == nullptr)
return true;
else if (node1 == nullptr || node2 == nullptr)
return false;
return StructureCmp(node1->left, node2->left) && Str1uctureCmp(node1->right, node2->right);
}
?8 求二叉樹(shù)的鏡像
對(duì)于每個(gè)結(jié)點(diǎn)，我們交換它的左右孩子即可。
void Mirror(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)下圖：
結(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)
return nullptr;
if (node == target1 || node == target2)
return node;
Node * left = FindLCA(node->left, target1, target2);
Node * right = FindLCA(node->right, target1, target2);
if (left && right) // 分別在左右子樹(shù)
return node;
return left ? left : right; // 都在左子樹(shù)或右子樹(shù)
}
?10 求任意兩結(jié)點(diǎn)距離
首先找到兩個(gè)結(jié)點(diǎn)的 LCA，然后分別計(jì)算 LCA 與它們的距離，最后相加即可。
int FindLevel(Node * node, Node * target)
{
if (node == nullptr)
return -1;
if (node == target)
return 0;
int level = FindLevel(node->left, target); // 先在左子樹(shù)找
if (level == -1)
level = FindLevel(node->right, target); // 如果左子樹(shù)沒(méi)找到，在右子樹(shù)找
if (level != -1) // 找到了，回溯
return level + 1;
return -1; // 如果左右子樹(shù)都沒(méi)找到
}
int DistanceNodes(Node * node, Node * target1, Node * target2)
{
Node * lca = FindLCA(node, target1, target2); // 找到最低公共祖先結(jié)點(diǎn)
int level1 = FindLevel(lca, target1);
int level2 = FindLevel(lca, target2);
return level1 + level2;
}
?11 找出二叉樹(shù)中某個(gè)結(jié)點(diǎn)的所有祖先結(jié)點(diǎn)
如果給定結(jié)點(diǎn) 5，則其所有祖先結(jié)點(diǎn)為 4,2,1。
bool FindAllAncestors(Node * node, Node * target)
{
if (node == nullptr)
return false;
if (node == target)
return true;
if (FindAllAncestors(node->left, target) || FindAllAncestors(node->right, target)) // 找到了
{
cout << node->data << " ";
return true; // 回溯
}
return false; // 如果左右子樹(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ù)的遍歷。
先看前序遍歷，步驟如下：
如果當(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)為空。
/* 前序遍歷 */
void PreOrderMorris(Node * root)
{
Node * cur = root;
Node * pre = nullptr;
while (cur)
{
if (cur->left == nullptr) // 步驟 1
{
cout << cur->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 << cur->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)為空。
/* 中序遍歷 */
void InOrderMorris(Node * root)
{
Node * cur = root;
Node * pre = nullptr;
while (cur)
{
if (cur->left == nullptr) //（1）
{
cout << cur->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 << cur->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)。
?
?
步驟如下：
如果當(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)為空。
struct Node
{
int data;
Node * left;
Node * right;
Node(int data_, Node * left_, Node * right_)
{
data = data_;
left = left_;
right = right_;
}
};
void ReversePrint(Node * from, Node * to)
{
if (from == to)
{
cout << from->data << " ";
return;
}
ReversePrint(from->right, to);
cout << from->data << " ";
}
void PostOrderMorris(Node * root)
{
Node * dummy = new Node(-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ù)前序中序推后序
以上面圖表為例，步驟如下：
根據(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) */
int pre_order_arry[n];
int in_order_arry[n];
void PrintPostOrder(int pos1, int pos2, int n)
{
if (n == 1)
{
cout << pre_order_arry[pos1];
return;
}
if (n == 0)
return;
int i = 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 << pre_order_arry[pos1];
}
? 當(dāng)然我們也可以根據(jù)前序和中序構(gòu)造出二叉樹(shù)，進(jìn)而求出后序。
/* 該函數(shù)返回二叉樹(shù)的根結(jié)點(diǎn) */
Node * Create(int pos1, int pos2, int n)
{
Node * p = nullptr;
for (int i = 0; i < n; i++)
{
if (pre_order_arry[pos1] == in_order_arry[pos2 + i])
{
p = new Node(pre_order_arry[pos1]);
p->left = Create(pos1 + 1, pos2, i);
p->right = Create(pos1 + i + 1, pos2 + i + 1, n - i - 1);
return p;
}
}
return p;
}
?
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）。如下圖：
首先若一個(gè)結(jié)點(diǎn)只有右孩子，肯定不是完全二叉樹(shù)；其次若只有左孩子或沒(méi)有孩子，那么接下來(lái)的所有結(jié)點(diǎn)肯定都沒(méi)有孩子，否則就不是完全二叉樹(shù)，因此設(shè)置 flag 標(biāo)記變量。
bool IsCBT(Node * node)
{
bool flag = false;
queue Q;
Q.push(node);
while (!Q.empty())
{
Node * p = Q.front();
Q.pop();
if (flag)
{
if (p->left || p->right)
return false;
}
else
{
if (p->left && p->right)
{
Q.push(p->left);
Q.push(p->right);
}
else if (p->right) // 只有右結(jié)點(diǎn)
return false;
else if (p->left) // 只有左結(jié)點(diǎn)
{
Q.push(p->left);
flag = true;
}
else // 沒(méi)有結(jié)點(diǎn)
flag = true;
}
}
return true;
}
?
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ù)。
?
int array[n]; // 長(zhǎng)度為 n 的序列，注意 begin 和 end 遵循的是左閉右閉原則
bool IsSequenceOfBST(int begin, int end)
{
if (end - begin <= 0)
return true;
int root_data = array[end]; // 數(shù)組尾元素為根結(jié)點(diǎn)
int i = begin;
for (; array[i] < root_data; i++) // 取得左子樹(shù)
;
int j = i;
for (; j < end; j++)
if (array[j] < root_data) // 此時(shí)右子樹(shù)應(yīng)該都大于根結(jié)點(diǎn)；若存在小于，直接 return false
return false;
return IsSequenceOfBST(begin, i - 1) && IsSequenceOfBST(i, end - 1); // 左右子樹(shù)是否都滿足
}
?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;
return node;
}
else // 步驟 2
{
if (node->parent == nullptr) // 步驟 2.1
return nullptr;
Node * p = node->parent; // 步驟 2.2
if (p->left == node) // 步驟 2.2.1
return p;
else // 步驟 2.2.2
{
while (p->right == node)
{
node = p;
p = p->parent;
if (p == nullptr)
return nullptr;
}
return p;
}
}
}
? 仔細(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;
}
return node;
}
? 上述的代碼是基于結(jié)點(diǎn)有 parent 指針的，若題意要求沒(méi)有 parent 呢？網(wǎng)上也有人給出了答案，個(gè)人覺(jué)得沒(méi)有什么價(jià)值，有興趣的朋友可以到這里查看。 而求前驅(qū)結(jié)點(diǎn)的話，只需把上述代碼的 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) return b;
if (b == nullptr) return a;
// 分別得到兩個(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;
return a;
}
/* 遞歸的解決二叉樹(shù)轉(zhuǎn)換為雙鏈表 */
Node * TreeToList(Node * node)
{
if (node == nullptr) return nullptr;
// 遞歸解決子樹(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);
return left_list;
}
?18 有序鏈表轉(zhuǎn)化為平衡的二分查找樹(shù)（Binary Search Tree）
我們可以采用自頂向下的方法。先找到中間結(jié)點(diǎn)作為根結(jié)點(diǎn)，然后遞歸左右兩部分。所以我們需要先找到中間結(jié)點(diǎn)，對(duì)于單鏈表來(lái)說(shuō)，必須要遍歷一邊，可以使用快慢指針加快查找速度。
struct TreeNode
{
int data;
TreeNode * left;
TreeNode * right;
TreeNode(int data_) { data = data_; left = right = nullptr; }
};
struct ListNode
{
int data;
ListNode * next;
ListNode(int data_) { data = data_; next = nullptr; }
};
TreeNode * SortedListToBST(ListNode * list_node)
{
if (!list_node) return nullptr;
if (!list_node->next) return (new TreeNode(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 = new TreeNode(slow->data);
// 分別遞歸左右兩部分
if (pre_slow)
{
pre_slow->next = nullptr;
mid->left = SortedListToBST(list_node);
}
mid->right = SortedListToBST(slow->next);
return mid;
}
? 由 f(n)=2f(frac n2)+frac n2f(n)=2f(2n)+2n 得，所以上述算法的時(shí)間復(fù)雜度為 O(nlogn)O(nlogn)。 不妨換個(gè)思路，采用自底向上的方法：
TreeNode * SortedListToBSTRec(ListNode *& list, int start, int end)
{
if (start > end) return nullptr;
int mid = start + (end - start) / 2;
TreeNode * left_child = SortedListToBSTRec(list, start, mid - 1); // 注意此處傳入的是引用
TreeNode * parent = new TreeNode(list->data);
parent->left = left_child;
list = list->next;
parent->right = SortedListToBSTRec(list, mid + 1, end);
return parent;
}
TreeNode * SortedListToBST(ListNode * node)
{
int n = 0;
ListNode * p = node;
while (p)
{
n++;
p = p->next;
}
return SortedListToBSTRec(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：
bool IsBST(Node * node, int min, int max)
{
if (node == nullptr)
return true;
if (node->data <= min || node->data >= max)
return false;
return IsBST(node->left, min, node->data) && IsBST(node->right, node->data, max);
}
IsBST(node, INT_MIN, INT_MAX);
? 方法 2： 利用二叉查找樹(shù)中序遍歷時(shí)元素遞增來(lái)判斷。
bool IsBST(Node * node)
{
static int pre = INT_MIN;
if (node == nullptr)
return true;
if (!IsBST(node->left))
return false;
if (node->data < pre)
return false;
pre = node->data;
return IsBST(node->right);
}
? 編輯：黃飛
?
?
?
工商網(wǎng)監(jiān)
評(píng)論