假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果都不含重復(fù)的數(shù)字哩照,重建二叉樹并輸出根節(jié)點(diǎn)架谎。二叉樹的定義如下:
struct BTreeNode
{
int value;
BTreeNode* pLeft;
BTreeNode* pRight;
};
解析:這道題看起來挺難矩欠,但其實(shí)可以采用遞歸的方法卑雁,找到規(guī)律了就很好解赶撰。前序遍歷序列的第一個(gè)節(jié)點(diǎn)即為整個(gè)樹的根贮尉,后面的序列的左半部分是左子樹琼了,而且遵循一樣的規(guī)則嫡丙;右半部分是右子樹莹汤,也同樣遵循一樣的規(guī)則快鱼。中序遍歷序列在中間可以找到根節(jié)點(diǎn),這個(gè)節(jié)點(diǎn)左邊的部分序列即為左子樹的序列纲岭,右邊部分的序列即為右子樹的序列攒巍。根據(jù)中序遍歷序列的左子樹序列長度可以在前序遍歷序列中找到左子樹和右子樹的分界點(diǎn)。找到了這個(gè)規(guī)律荒勇,寫出代碼就很容易了柒莉。
代碼肯定采用遞歸的寫法。首先從前序序列中讀取第一個(gè)節(jié)點(diǎn)沽翔,即為當(dāng)前樹的根節(jié)點(diǎn)兢孝,構(gòu)建這個(gè)根節(jié)點(diǎn)。然后在中序序列中找到這個(gè)根節(jié)點(diǎn)仅偎,該節(jié)點(diǎn)的左半部分即為左子樹的中序遍歷序列跨蟹,該序列的長度即為左子樹的節(jié)點(diǎn)個(gè)數(shù)。從前序序列的第二個(gè)開始橘沥,根據(jù)左子樹節(jié)點(diǎn)個(gè)數(shù)即可推斷出剩余的前序序列中多少屬于左子樹窗轩,剩下的屬于右子樹。至于邊界情況座咆,當(dāng)前序序列和中序序列都只剩一個(gè)節(jié)點(diǎn)痢艺,那就說明構(gòu)建快要完成了,如果判斷前序序列的這個(gè)節(jié)點(diǎn)和中序序列的這個(gè)節(jié)點(diǎn)是同一個(gè)節(jié)點(diǎn)介陶,那就說明輸入的遍歷序列合法堤舒。
答案:
BTreeNode* ConstructCore
(int* startPreOrder, int* endPreOrder, int* startInOrder, int* endInOrder)
{
//construct the root
auto root = new BTreeNode();
root->pLeft = root->pRight = nullptr;
root->value = *startPreOrder;
//there's only one node left
if (startPreOrder == endPreOrder)
{
if (startInOrder==endInOrder && *startPreOrder==*startInOrder)
return root;
else throw exception();
}
//find the root in the InOrder sequence
int *rootInOrder = startInOrder;
while (*rootInOrder != *startPreOrder && rootInOrder<=endInOrder)
++rootInOrder;
if (rootInOrder==endInOrder && *rootInOrder!=*startPreOrder)
throw exception();
//mark left subtree and right subtree
int *startLeftTreePreOrder = startPreOrder+1;
int *endLeftTreePreOrder = startPreOrder+(rootInOrder-startInOrder);
int *startLeftTreeInOrder = startInOrder;
int *endLeftTreeInOrder = rootInOrder-1;
int *startRightTreePreOrder = endLeftTreePreOrder+1;
int *endRightTreePreOrder = endPreOrder;
int *startRightTreeInOrder = rootInOrder+1;
int *endRightTreeInOrder = endInOrder;
//recursively construct left subtrees and right subtrees
if (*rootInOrder == *startPreOrder && rootInOrder>startInOrder)
root->pLeft =
ConstructCore(startLeftTreePreOrder, endLeftTreePreOrder,
startLeftTreeInOrder, endLeftTreeInOrder);
if (*rootInOrder == *startPreOrder && rootInOrder<endInOrder)
root->pRight =
ConstructCore(startRightTreePreOrder, endRightTreePreOrder,
startRightTreeInOrder, endRightTreeInOrder);
return root;
}
BTreeNode* Construct(int* preOrder, int* inOrder, int length)
{
if (preOrder == nullptr || inOrder == nullptr || length <= 0)
return nullptr;
return ConstructCore(preOrder, preOrder+length-1,
inOrder, inOrder+length-1);
}