编程之美 3.9 重建二叉树

题目描述： 

给定一棵二叉树，假定每个节点都用唯一的字符表示，具体结构如下：

struct NODE {
  NODE* pLeft;
  NODE* pRight;
  char chValue;
};

假设已经有了前序遍历和中序遍历结果，希望通过一个算法重建这棵树。
给定函数的定义如下：
void Rebuild(char* pPreOrder, char* pInOrder, int nTreeLen, NODE** pRoot);
参数

pPreOrder:前序遍历结果的字符串数组。
pInOrder: 中序遍历结果的字符串数组。
nTreeLen: 树的长度。
pRoot:     根据前序和中序遍历结果重新构建树的根节点。

例如
前序遍历结果：a b d c e f
中序遍历结果：d b a e c f

分析与解法

递归实现
递归结束条件是长度小于1，此时令*pRoot=NULL即可。
递归主体中，在中序遍历结果中找前序结果的第一个字符，找到后记录其下标为index，
       如果找不到说明前序遍历和中序遍历有问题，说明错误信息，然后直接返回。找到index后，新建一个节点，让*pRoot指向它，其数值为前序的第一个字符，
然后递归求*pRoot的左孩子和右孩子。
递归左孩子：Rebuild( pPreOrder+1，pInOrder, index, &((*pRoot)->pLeft) )
递归右孩子：Rebuild( pPreOrder+index+1, pInOrder+index+1, nTreeLen-index-1, &((*pRoot)->pRight) ) 

#include <iostream>
#include<stdio.h>
using namespace std;

struct NODE {
  NODE* pLeft;
  NODE* pRight;
  char chValue;
};

void Rebuild(char* pPreOrder, char* pInOrder, int nTreeLen, NODE** pRoot) {
  if(nTreeLen<= 0) 
  {  
    *pRoot = NULL;
    return;
  }
  else 
  {  
    int index = 0;
    while(index<nTreeLen&&pPreOrder[0]!=pInOrder[index])
      index++;
      
    if(index>=nTreeLen) 
	{
      cout << "前序和中序字符串不匹配，有问题" << endl;
      cout << "在中序字符串中，找不到：" << pPreOrder[0] << endl;
      return;
    }
    else 
	{
      *pRoot = new NODE;
      (*pRoot)->chValue = pPreOrder[0];
      Rebuild(pPreOrder+1, pInOrder, index, &((*pRoot)->pLeft));
      Rebuild(pPreOrder+index+1, pInOrder+index+1, nTreeLen-index-1, &((*pRoot)->pRight) );
    }
  }  
}

void BaOrder(NODE *tree)  
{  
    if(tree!=NULL)  
    {  
        BaOrder(tree->pLeft);   
        BaOrder(tree->pRight);
		printf("%c ",tree->chValue); 
    }  
}

int main() {
  char* pPreOrder = "abdcef";
  char* pInOrder = "dbaecf";
  NODE* pRoot;
  Rebuild(pPreOrder, pInOrder, strlen(pPreOrder), &pRoot);
  BaOrder(pRoot);
  //后序 d b e f c a 
  return 0;
}

扩展问题1：

如果前序和中序遍历的字母有重复的，那么怎么构造所有可能的解呢？

       搜索所有可能的情况，并调用扩展问题2的解决方案，判断此情况是否合理（剪枝操作），
如果合法，则构造解

扩展问题2：

如何判断给定的前序遍历和中序遍历的结果是合理的？
        递归算法实现，分别遍历左右子树，递归中迭代查找左右子树的长度，类似于书中的方法。
http://blog.csdn.net/luyafei_89430/article/details/12967411

扩展问题3：

如果知道前序和后序的结果，能重构二叉树吗？

        前序+后序，这个组合是无法重建确定的二叉树的。
对于满二叉树，利用子树节点的排列顺序能区分开左右子树节点集合，构建是没有问题的。但一旦有单个叶子的节点存在，则无法确定叶子是左儿子还是右儿子。因为无论是前序还是后序序列，都无法体现单个儿子情况下，儿子的位置。前序会将左右子树的点置于节点之后，后序则是将左右子树的点置于节点之前。

举个简单的反例：
        给出如下的前序序列和后序序列： preorder: A, B; postorder: B, A能构建的二叉树有两种可能，1.A 是根节点，B 是 A 左儿子； 2.A 是根节点， B 是 A 的右儿子。无法得到一个唯一的结果。

总结
中序遍历配合另外任何一个遍历，能重建二叉树。其他的任意两个序列的组合都不能唯一的确定重建的二叉树。

附：已知后序和中序：

void ReBuild_AftIn(char *pAftOrder, char *pInOrder, int nTreeLen, NODE **pRoot)
{
    if (pAftOrder == NULL || pInOrder == NULL)
    {
        return;
    }
    
    NODE *pTemp = new NODE;
    pTemp->chValue = *pAftOrder;
    pTemp->pLeft   = NULL;
    pTemp->pRight  = NULL;
    
    if (*pRoot == NULL)
    {
        *pRoot = pTemp;
    }
    
    if (nTreeLen == 1)
    {
        return;
    }
    
    int nLeftLen = CharInStrFirstPos(*pAftOrder, pInOrder, nTreeLen);
    assert(nLeftLen != -1);
    int nRightLen = nTreeLen - nLeftLen -1;
    
    if (nLeftLen > 0)
    {
        ReBuild_AftIn(pAftOrder + nRightLen + 1, pInOrder, nLeftLen, &((*pRoot)->pLeft));
    }
    
    if (nRightLen > 0)
    {
        ReBuild_AftIn(pAftOrder + 1, pInOrder + nLeftLen + 1,
            nRightLen, &((*pRoot)->pRight));
    }
}