2019-08-05.md

毎日一题 - 105.从前序与中序遍历序列构造二叉树

信息卡片

• 时间：2019-08-05
• 题目链接：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

• tag：Tree Array

题目描述

根据一棵树的前序遍历与中序遍历构造二叉树。

注意:
你可以假设树中没有重复的元素。

例如，给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：

    3
   / \
  9  20
    /  \
   15   7

参考答案

递归构造二叉树，时间复杂度O(n)

关键在于前序遍历和中序遍历的特性:

• 前序遍历：根节点是首元素
• 中序遍历：根节点左侧的值是其左子树，右侧的值是其右子树

因此，我们首先要得到从前序序列中获取根节点，然后遍历中序序列，找到根节点的位置，以此直到其左子树和右子树的范围。当我们得到其左子树之后，事情就开始重复了，我们仍然需要根据前序序列中找到这颗左子树的根节点，然后再根据中序序列得到这颗左子树根节点的左右子树，右子树同理。因此实际上就是个回溯。

struct TreeNode* _buildTree(int* preorder, int* pindex, int* inorder, int inbegin, int inend)
{
    if(inbegin>inend)//区间不存在，空树
    {
        return NULL;
    }
    struct TreeNode* root=(struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val=preorder[*pindex];
    (*pindex)++;
    if(inbegin==inend)//区间只有一个结点，就是根结点
    {
        root->val=inorder[inbegin];
        root->left=NULL;
        root->right=NULL;
        return root;
    }
    //区间正常
    int rootindex=inbegin;
    while(rootindex<=inend)//用前序的根划分中序为两个子区间
    {
        if(inorder[rootindex]==root->val)
        {
            break;
        }
        else
        {
            ++rootindex;
        }
    }
    //递归创建左子树
    root->left= _buildTree(preorder, pindex, inorder, inbegin, rootindex-1);
    //递归创建右子树
    root->right= _buildTree(preorder, pindex, inorder, rootindex+1, inend);
    return root;
}

其他优秀解答

暂缺