《編程之美》讀書筆記19： 3.9 重建二叉樹

對根節點a以及先序遍歷次序P和中序遍歷次序I，查找a在I中的位置，將I分為兩部分，左邊部分的元素都在a的左子樹上，右邊的元素都在a的右子樹上，因而可以確定a的左子樹節點數和a的右子樹節點數，再結合P，可以確定a的左孩子和右孩子，以及各個孩子的先序和中序遍歷次序。

由于已經知道節點數，可以事先分配好內存，可以按先序遍歷次序連續存放節點。

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)，有可能出現棧溢出，可以修改代碼，減少一次遞歸調用，實現棧深度為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;
  
  // 如果節點為空，把當前節點復制到根節點
  if(*pRoot == NULL)
  {
       *pRoot = pTemp;
  }

可能引起內存泄漏（當*pRoot!=NULL，新申請的內存沒釋放），注釋也不對（不是復制節點，而是更改指針指向新建的節點）。另外，頻繁的new，極有可能會產生內存碎片。當節點很小時，內存浪費很嚴重（每new一次都要額外分配空間儲存相關信息）。