力扣105. 从前序与中序遍历序列构造二叉树_力扣105题c++解法

力扣105. 从前序与中序遍历序列构造二叉树

题目描述

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

输入输出样例

输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]

1
2
3

输入: preorder = [-1], inorder = [-1]
输出: [-1]
1
2

解法，使用迭代进行

unordered_map<int,int>hashInorder;


TreeNode *myBuildTree(const vector<int>&preorder,const vector<int>&inorder,
        int preorderLeft, int preorderRight,int inorderLeft,int inorderRight)
{
    //当左边的值大于右边的值时
    if(preorderLeft>preorderRight||inorderLeft>inorderRight)
    {
        return nullptr;
    }

    //由前序遍历的定义可以知道，前序遍历的第一个结点就是根节点
    int preorderRoot=preorderLeft;
    //从根节点列表中查找对应的根节点的位置
    int inorderRoot=hashInorder[preorder[preorderRoot]];

    //首先建立根节点
    TreeNode *root=new TreeNode(preorder[preorderRoot]);

    //获得对应当前根节点左子树结点的数目
    int subtreeLeftLength=inorderRoot-inorderLeft;

    //递归构造左子树，并连接到根节点
    //先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素
    root->left=myBuildTree(preorder,inorder,preorderLeft+1,preorderLeft+subtreeLeftLength,inorderLeft,inorderRoot-1);
      // 递归地构造右子树，并连接到根节点
        // 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素
    root->right=myBuildTree(preorder,inorder,preorderLeft+subtreeLeftLength+1,preorderRight,inorderRoot+1,inorderRight);
    return root;
}



//利用hash表保存中序遍历值的坐标，方便之后的查找的时间复杂度降低
TreeNode * buildTree(vector<int>&preorder,vector<int>&inorder)
{
    int length=preorder.size();
    for(int i=0;i<length;i++)
    {
        hashInorder[inorder[i]]=i;
    }
    return myBuildTree(preorder,inorder,0,length-1,0,length-1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44