《剑指Offer》面试题7

 

1 问题

题目：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1, 2, 4, 7, 3, 5, 6, 8}和中序遍历序列{4, 7, 2, 1, 5, 3, 8, 6}，则重建出
 

    /*                  1
     *            2            3           
     *         4            5      6       
     *           7               8

 

2 分析（递归思想）

1.根据二叉树前序遍历的特点，遍历结果中第一个节点是树的根节点，确定根节点的值val。
2.然后根据val，在中序遍历的结果中寻找根节点的位置，根据规律：左子树节点 -> 根节点 -> 右子树节点，确定左右节点的数量
3.再根据左右节点的数量，得出前序遍历结果：根节点 -> 左子树节点 -> 右子树节点
有了上述规律，总结递推公式（分别对左右子树进行，不断缩小问题范围）、回归条件（没有左右子树了，所有根节点确认完毕）
 

3 代码

BinaryTreeNode* ConstructCore(int* startPreorder, int* endPreorder, int* startInorder, int* endInorder);

//功能：根据二叉树前序和中序遍历结果，重建二叉树
//输入：preorder前序遍历数组首地址、inorder中序遍历数组首地址、length节点个数
//返回：根节点指针
BinaryTreeNode* 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);
}

//功能：递归实现二叉树重建
//输入： startPreorder前序遍历数组首地址、endPreorder前序遍历数组尾地址	
//		startInorder中序遍历数组首地址、endInorder中序遍历数组尾地址
//返回：根节点指针
BinaryTreeNode* ConstructCore(int* startPreorder, int* endPreorder, int* startInorder, int* endInorder)
{
    // 1.确定根节点为前序遍历结果的第一个元素
    int rootValue = startPreorder[0];
    BinaryTreeNode* root = new BinaryTreeNode();
    root->m_nValue = rootValue;
    root->m_pLeft = root->m_pRight = nullptr;

    if(startPreorder == endPreorder)
    {//考虑只有一个根节点的情况
        if(startInorder == endInorder && *startPreorder == *startInorder)
            return root;
        else
            throw std::exception("Invalid input.");
    }

    // 2.在中序遍历中找到根结点的值
    int* rootInorder = startInorder;
    while(rootInorder <= endInorder && *rootInorder != rootValue)
        ++ rootInorder;

    if(rootInorder == endInorder && *rootInorder != rootValue)
        throw std::exception("Invalid input.");

    // 3.在前序遍历结果中确定左子树节点的数量
    int leftLength = rootInorder - startInorder;
    int* leftPreorderEnd = startPreorder + leftLength;
    if(leftLength > 0)
    {//4.对左子树进行递归，构建左子树
        
        root->m_pLeft = ConstructCore(startPreorder + 1, leftPreorderEnd, 
            startInorder, rootInorder - 1);
    }
    if(leftLength < endPreorder - startPreorder)
    {//对右子树进行递归，构建右子树
        
        root->m_pRight = ConstructCore(leftPreorderEnd + 1, endPreorder,
            rootInorder + 1, endInorder);
    }

    return root;
}