《編程之美》讀書筆記19： 3.9 重建二叉樹
對(duì)根節(jié)點(diǎn)a以及先序遍歷次序P和中序遍歷次序I，查找a在I中的位置，將I分為兩部分，左邊部分的元素都在a的左子樹上，右邊的元素都在a的右子樹上，因而可以確定a的左子樹節(jié)點(diǎn)數(shù)和a的右子樹節(jié)點(diǎn)數(shù)，再結(jié)合P，可以確定a的左孩子和右孩子，以及各個(gè)孩子的先序和中序遍歷次序。
由于已經(jīng)知道節(jié)點(diǎn)數(shù)，可以事先分配好內(nèi)存，可以按先序遍歷次序連續(xù)存放節(jié)點(diǎn)。
rebuild_tree_1
struct Node 
{
Node* left;
Node* right;
char data;
};
void rebuild(char preorder[], char inorder[], Node result[], size_t size)
{
result->data = *preorder;
result->left=NULL;
result->right=NULL;
char *p = inorder;
size_t left_size=0;
while (left_size<size && *p++!=*preorder) ++left_size;
assert (left_size<size);
size_t right_size = size-1-left_size;
if (left_size) {
result->left=result+1;
rebuild(preorder+1, inorder, result+1, left_size);
}
if (right_size) {
result->right=result+left_size+1;
rebuild(preorder+left_size+1, inorder+left_size+1,
result+left_size+1, right_size);
}
}
上面的代碼，棧深度是O(n)，有可能出現(xiàn)棧溢出，可以修改代碼，減少一次遞歸調(diào)用，實(shí)現(xiàn)棧深度為O(lg n)。
rebuild_tree_2
void rebuild2(char preorder[], char inorder[], Node result[], size_t size)
{
while (1){
result->data = *preorder;
result->left=NULL;
result->right=NULL;
char *p = inorder;
size_t left_size=0;
while (left_size<size && *p++!=*preorder) ++left_size;
assert (left_size<size);
size_t right_size = size-1-left_size;
if (left_size==0 && right_size==0) break;
if (left_size<right_size) {
if (left_size) {
result->left=result+1;
rebuild2(preorder+1, inorder, result+1, left_size);
}
result->right=result+left_size+1;
preorder += left_size+1;
inorder += left_size+1;
result += left_size+1;
size = right_size;
} else {
if (right_size) {
result->right=result+left_size+1;
rebuild2(preorder+left_size+1, inorder+left_size+1,
result+left_size+1, right_size);
}
if (left_size) {
result->left=result+1;
++preorder;
++result;
size = left_size;
}
}
}
}
書上的代碼（P246）：
NODE* pTemp = new NODE;
pTemp -> chValue = *pPreOrder;
pTemp -> pLeft = NULL;
pTemp -> pRight = NULL;
// 如果節(jié)點(diǎn)為空，把當(dāng)前節(jié)點(diǎn)復(fù)制到根節(jié)點(diǎn)
if(*pRoot == NULL)
{
*pRoot = pTemp;
}
可能引起內(nèi)存泄漏（當(dāng)*pRoot!=NULL，新申請(qǐng)的內(nèi)存沒釋放），注釋也不對(duì)（不是復(fù)制節(jié)點(diǎn)，而是更改指針指向新建的節(jié)點(diǎn)）。另外，頻繁的new，極有可能會(huì)產(chǎn)生內(nèi)存碎片。當(dāng)節(jié)點(diǎn)很小時(shí)，內(nèi)存浪費(fèi)很嚴(yán)重（每new一次都要額外分配空間儲(chǔ)存相關(guān)信息）。