64. 用中序和后序遍历序列构建二叉树

RT

final case class TreeNode(var value: Int, var left: TreeNode = null, var right: TreeNode = null)

  def buildTree(in: IndexedSeq[Int], post: IndexedSeq[Int]): TreeNode = {
    val inPos = in.zipWithIndex.toMap

    def build(postStart: Int, postEnd: Int, inStart: Int): TreeNode = {
      if (postStart > postEnd) return null

      val root = TreeNode(post(postEnd))
      val rootIdx = inPos(root.value)
      val leftCount = rootIdx - inStart
      root.left = build(postStart, postStart + leftCount - 1, inStart)
      root.right = build(postStart + leftCount, postEnd - 1, rootIdx + 1)
      root
    }

    build(0, post.length - 1, 0)
  }

Unit test:

      buildTree(Vector(2, 1, 8, 4, 16), Vector(2, 8, 16, 4, 1)) should be(
        TreeNode(1, TreeNode(2), TreeNode(4, TreeNode(8), TreeNode(16))))