算法练习--021：从中序与后序遍历序列构造二叉树

1. 题目

给定两个整数数组inorder和postorder ，其中inorder是二叉树的中序遍历，postorder是同一棵树的后序遍历，请构造并返回这颗二叉树

示例1：

输入：inorder = [9, 3, 15, 20, 7], postorder = [9, 15, 7, 20, 3]
输出：[3, 9, 20, null, null, 15, 7]

   //中序和后序遍历验证二叉树
    var indexMap2 = [Int:Int]()
      func buildTreePostAndIn(_ postorder: [Int], _ inorder: [Int]) -> TreNode? {
      // 构造哈希映射，帮助我们后续可以快速定位根节点
      for i in 0..<postorder.count {
        indexMap[inorder[i]] = i
      }
      return submethod(postorder,inorder,0,postorder.count-1,0,inorder.count-1)
    }
      func submethod(_ postorder: [Int], _ inorder: [Int], _ postorder_left:Int, _ postorder_right: Int,_ inorder_left:Int, _ inorder_right:Int) -> TreNode? {
      if postorder_left > postorder_right {
        return nil
      }
      // 后序遍历中的最后一个节点就是根节点
      let postorder_root = postorder_right
      // 在中序遍历中定位根节点
      let inorder_root = indexMap[postorder[postorder_root]]!
      // 先把根节点建立出来
          let root2 = TreNode.init(t: postorder[postorder_root])
      // 得到左子树中的节点数目
      let size_left_subtree = inorder_root - inorder_left
      // 递归地构造左子树，并连接到根节点
      // 后序遍历中「从 左边界 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素
          root2.left = submethod(postorder, inorder, postorder_left, postorder_left + size_left_subtree-1, inorder_left, inorder_root - 1)
      // 递归地构造右子树，并连接到根节点
      // 后序遍历中「从 左边界+左子树节点数目 开始到 右边界-1」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素
          root2.right = submethod(postorder, inorder, postorder_left + size_left_subtree, postorder_right-1, inorder_root + 1, inorder_right)
      return root2;
    }