题目

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

注意:

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

例如，给出

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

    3
   / \
  9  20
    /  \
   15   7

方案一

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func buildTree(inorder []int, postorder []int) *TreeNode {
    if len(inorder) == 0 {
        return nil
    }
    if len(inorder) == 1 {
        return &TreeNode {
            Val: inorder[0],
        }
    }

    root := &TreeNode {
        Val: postorder[len(postorder) - 1],
    }

    inorder_left, inorder_right := splitInorder(inorder, root.Val)
    root.Left = buildTree(inorder_left, getPostorder(postorder, inorder_left))
    root.Right = buildTree(inorder_right, getPostorder(postorder, inorder_right))

    return root
}

func splitInorder(inorder []int, ele int) ([]int, []int) {
    split_i := 0
    for i, e := range inorder {
        if e == ele {
            split_i = i
        }
    }

    return inorder[:split_i], inorder[split_i+1:]
}

func getPostorder(postorder, inorder []int) []int {
    if len(inorder) == 0 {
        return []int{}
    }
    // 构建 map
    m := map[int]bool{}
    for _, in := range inorder {
        m[in] = true
    }

    // 寻找 后序遍历
    ret := []int{}
    for _, post := range postorder {
        if _, ok := m[post]; ok {
            ret = append(ret, post)
        }
    }
    return ret
}

• 时间复杂度
• 构建理论如下：

https://jingyan.baidu.com/article/cdddd41cb8d79753ca00e144.html

再次查阅原理可得到，上述 getPostorder 可直接简化，代码如下：

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func buildTree(inorder []int, postorder []int) *TreeNode {
    if len(inorder) == 0 {
        return nil
    }

    root := &TreeNode {
        Val: postorder[len(postorder) - 1],
    }

    index := getSplitInorderIndex(inorder, root.Val)
    root.Left = buildTree(inorder[:index], postorder[:index])
    root.Right = buildTree(inorder[index+1:], postorder[index:len(postorder)-1])

    return root
}

func getSplitInorderIndex(inorder []int, ele int) int {
    for i, e := range inorder {
        if e == ele {
            return i
        }
    }

    return -1
}

原文

https://leetcode-cn.com/explore/learn/card/data-structure-binary-tree/4/conclusion/15/