前言：
现时同学们对“树的后根遍历序列与其对应的二叉树的后序遍历序列相同”可能比较讲究，我们都需要了解一些“树的后根遍历序列与其对应的二叉树的后序遍历序列相同”的相关内容。那么小编同时在网摘上收集了一些对于“树的后根遍历序列与其对应的二叉树的后序遍历序列相同””的相关内容，希望你们能喜欢，大家一起来了解一下吧！题目
根据一棵树的中序遍历与后序遍历构造二叉树。
注意:你可以假设树中没有重复的元素。
例如，给出
中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]
返回如下的二叉树：
3
/ \
9 20
/ \
15 7
解题思路分析
1、递归；时间复杂度O(n)，空间复杂度O(n)
func buildTree(inorder []int, postorder []int) *TreeNode { last := len(postorder) - 1 for k := range inorder { if inorder[k] == postorder[last] { return &TreeNode{ Val: postorder[last], Left: buildTree(inorder[0:k], postorder[0:k]), Right: buildTree(inorder[k+1:], postorder[k:last]), } } } return nil}2、递归；时间复杂度O(n)，空间复杂度O(n)
func buildTree(inorder []int, postorder []int) *TreeNode { if len(postorder) == 0 { return nil } return helper(inorder, postorder)}func helper(inorder []int, postorder []int) *TreeNode { var root *TreeNode last := len(postorder) - 1 for k := range inorder { if inorder[k] == postorder[last] { root = &TreeNode{Val: postorder[last]} root.Left = helper(inorder[0:k], postorder[0:k]) root.Right = helper(inorder[k+1:], postorder[k:last]) } } return root}3、迭代；时间复杂度O(n)，空间复杂度O(n)
func buildTree(inorder []int, postorder []int) *TreeNode { if postorder == nil || len(postorder) == 0 { return nil } last := len(postorder) - 1 root := &TreeNode{ Val: postorder[last], } length := len(postorder) stack := make([]*TreeNode, 0) stack = append(stack, root) index := last for i := length - 2; i >= 0; i-- { value := postorder[i] node := stack[len(stack)-1] if node.Val != inorder[index] { node.Right = &TreeNode{Val: value} stack = append(stack, node.Right) } else { for len(stack) > 0 && stack[len(stack)-1].Val == inorder[index] { node = stack[len(stack)-1] stack = stack[:len(stack)-1] index-- } node.Left = &TreeNode{Val: value} stack = append(stack, node.Left) } } return root}总结Medium题目，考察二叉树知识点，其中本题递归的方法比较好理解，迭代方法稍微难理解一点
解题思路同leetcode105 从前序与中序遍历序列构造二叉树
版权声明：
本站文章均来自互联网搜集，如有侵犯您的权益，请联系我们删除，谢谢。
