剑指OFFER面试题6：根据前序和中序构建二叉树

根据前序和中序构建二叉树

---

前提摘要

根据前序（preorder）中序（inorder）构建二叉树的原理请见书本
本代码同样通过递归实现，但传入的参数稍有不同。分别为preorder数组的首地址、子树对应preorder区间的初始下标、inorder数组的首地址、子树对应inorder区间的初始下标和子树对应区间的长度。根据这五个参数，我们可以确定子树所在的区间。
显然，在preorder数组和inorder数组中，子树对应的区间长度是相等的，只是顺序不同，因此剩下的工作就是找出子树对应区间分别在preorder数组和inorder的位置。

nRootValueOffset的作用

nRootValueOffset记录的是当前区间父节点在inoder数组中相对的inorder_start的偏移，例如未递归前父节点值为1，在inorder数组中相对inorder_start的偏移为3。根据这个值我们可以判断在inorder数组中位于父节点左边的区间属于左子树，右边的区间属于右子树。而且左子树的区间大小就是等于nRootValueOffset，右子树区间大小等于总区间大小nLength减去偏移量和父节点，即nLength-1-nRootValueOffset。

如何判断一个节点是否有左子树或者右子树

在inorder数组中：

1. 发生偏移，则一定存在左子树，且左子树位于偏移坐标左边
2. 如果偏移量达到最大，即nLength-1，则不存在右子树；反之若偏移值未达到最大则存在右子树

寻找preoder数组中左子树区间和右子树区间的起始位置

preorder数组结构为"父节点+左子树+右子树"，因此左子树区间的起始一定在父节点的下一个位置，而父节点就是preorder数组中当前区间的起始位置：preorder_start，左子树区间起始位置为preorder_start+1，右子树区间初始位置为左子树区间起始位置加上字字数长度：preorder_start+nRootValueOffset+1

寻找inorder数组中左子树区间和右子树区间的起始位置

inorder数组结构为”左子树+父节点+右子树”，容易得到左子树区间起始位置为当前区间起始位置：inorder_start，右子树区间起始位置为当前区间起始位置加上左子树长度加上父节点：inorder_start+nRootValueOffset+1

代码如下：

BinaryTreeNode* buildTree(int preorder[],int preorder_start,int inorder[],int inorder_start,int nLength){
    if(preorder==NULL || inorder==NULL || preorder_start<=0 || inorder_start<=0 || nLength<=0 )
        return NULL;
    BinaryTreeNode* root = new BinaryTreeNode();
    root->m_nValue = preorder[preorder_start];
    int nRootValueOffset=0; 
    
    //找出偏移值
    for(int i=inorder_start;i<inorder_start+nLength;i++){
        if (inorder[i]==root->m_nValue) break;
        nRootValueOffset++;
    }
    if(nRootValueOffset>0)
        root->m_pLeftChild=buildTree(preorder,preorder_start+1,inorder,inorder_start,nRootValueOffset);
    else root->m_pLeftChild=NULL;

    if(nRootValueOffset<nLength-1)
        root->m_pRightChild=buildTree(preorder,preorder_start+nRootValueOffset+1,inorder,inorder_start+nRootValueOffset+1,nLength-1-nRootValueOffset);
    else root->m_pRightChild=NULL;

    return root;
}