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

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

  1. 由先序序列第一个pre[0]在中序序列中找到根节点位置gen
  2. 以gen为中心遍历
    • 0~gen左子树
      • 子中序序列：0~gen-1，放入vin_left[]
      • 子先序序列：1~gen放入pre_left[]，+1可以看图，因为头部有根节点
    • gen+1~vinlen为右子树
      • 子中序序列：gen ~ vinlen-1放入vin_right[]
      • 子先序序列：gen ~ vinlen-1放入pre_right[]
  3. 由先序序列pre[0]创建根节点
  4. 连接左子树，按照左子树子序列递归（pre_left[]和vin_left[]）
  5. 连接右子树，按照右子树子序列递归（pre_right[]和vin_right[]）
  6. 返回根节点

复杂度分析

  • 时间复杂度：O(n)，其中 n 是树中的节点个数。
  • 空间复杂度：O(n)，除去返回的答案需要的 O(n) 空间之外，我们还需要使用 O(n) 的空间存储哈希映射，以及 O(h)（其中 hh 是树的高度）的空间表示递归时栈空间。这里 h < n，所以总空间复杂度为 O(n)。


  1. //递归：实际没用到哈希表，所以时间复杂度 On^2 ?
  2.  * 1. 从题目可知是一道二叉树相关问题,首先想到递归或栈结构
  3.  * 2. 构建二叉树,二叉树具有递归结构性,自然想到使用递归来构建二叉树
  4.  * 3. 如何构建递归子问题? 根据前序遍历可以快速底定位根的位置,中序遍历可以划分出左子树与右子树的元素集合
  5.  * 4. 递归基是什么? 中序数组被划分为空,说明已经到达叶子节点返回nil即可
  6.  * 5. 递归体如何实现? 搜索划分点 + 构建二叉树
  10. func buildTree(preorder []int, inorder []int) *TreeNode {
  11.     if len(preorder) == 0 || len(inorder) == 0 {
  12.         return nil
  13.     }
  15.     root := &TreeNode{preorder[0] , nil , nil }     //根据前序，找到根节点，开始划分三部分
  17.     i := 0    ·
  18.     for i = 0; i < len(inorder); i++ {
  19.         if inorder[i] == preorder[0] {      //中序 在inorder找到 根结点（上文）== 递归的核心
  20.             break
  21.         }
  22.     }
  24.      //中序 在左右子树继续找根节点，递归，传参（长度，起始点）
  25.      //前序（根，左右）；中序（左，根，右），参考图
  26.     root.Left = buildTree(preorder[1: len(inorder[:i]) + 1], inorder[:i])   //在中序【i】的左边
  27.     root.Right = buildTree(preorder[len(inorder[:i]) + 1:], inorder[i+1:]) //在中序【i】的右边
  29.     return root
  30. }
//递归升级版：更好理解
func buildTree(preorder []int, inorder []int) *TreeNode {
    if len(preorder) == 0 || len(inorder) == 0 {
        return nil
    }

    root := &TreeNode{preorder[0] , nil , nil }     //根据前序，找到根节点，开始划分三部分

    // 中顺序列找根结点
    var Mid_Node int
    for i, inorder_i :=  range inorder {
        if inorder_i == preorder[0] {
            Mid_Node = i
            break
        }
    }

     //中序 在左右子树继续找根节点，递归，传参（长度，起始点）,左闭右开区间
     //前序（根，左右）；中序（左，根，右），参考图
    root.Left = buildTree(preorder[1: Mid_Node + 1], inorder[0: Mid_Node])   //在中序【i】的左边
    root.Right = buildTree(preorder[Mid_Node + 1:], inorder[Mid_Node + 1:]) //在中序【i】的右边

    return root
}

//递归+ 哈希，优化时间
func myBuildTree(m map[int]int, preorder, inorder []int, preLeft, preRight, inLeft, inRight int) *TreeNode {
    if preLeft > preRight {
        return nil
    }

    root := &TreeNode{0, nil, nil}
    root.Val = preorder[preLeft]

    pIndex := m[preorder[preLeft]]        //1,中序的中点=root
    preLeftTreeRight := pIndex + preLeft - inLeft    //1,前序 左子树的最后一位，详见图解

    root.Left = myBuildTree(m, preorder, inorder, preLeft+1, preLeftTreeRight, inLeft, pIndex-1)
    root.Right = myBuildTree(m, preorder, inorder, preLeftTreeRight+1, preRight, pIndex+1, inRight)
    return root                //2,遍历前序，存入哈希表
}

//3,主体函数，层层递归
func buildTree(preorder []int, inorder []int) *TreeNode {
    if len(preorder) == 0 {
        return nil
    }

    m := make(map[int]int)
    for i, v := range inorder {
        m[v] = i
    }

    root := myBuildTree(m, preorder, inorder, 0, len(preorder)-1, 0, len(inorder)-1)

    return root
}

//迭代，时空都是On
func buildTree(preorder []int, inorder []int) *TreeNode {
    if len(preorder) == 0 {
        return nil
    }

    root := &TreeNode{preorder[0], nil, nil}
    stack := []*TreeNode{}
    stack = append(stack, root)

    var inorderIndex int
    for i := 1; i < len(preorder); i++ {
        preorderVal := preorder[i]
        node := stack[len(stack)-1]

        if node.Val != inorder[inorderIndex] {
            node.Left = &TreeNode{preorderVal, nil, nil}
            stack = append(stack, node.Left)

        } else {
            for len(stack) != 0 && stack[len(stack)-1].Val == inorder[inorderIndex] {
                node = stack[len(stack)-1]
                stack = stack[:len(stack)-1]
                inorderIndex++
            }

            node.Right = &TreeNode{preorderVal, nil, nil}
            stack = append(stack, node.Right)
        }
    }
    return root
}