Leetcode 剑指 Offer 07. 重建二叉树

leetcode

题目描述

法2

中序递归:
遍历方法前序中序后序代表的是根节点的位置 中序遍历,根节点在中间,前序遍历根节点在前面,也就是,拿到前序遍历的第一个数据就是根节点,在中序遍历中查找根节点位置,在左侧的就是左子树元素,在右侧的就是右子树元素,依次递归左子树的前序元素p[1:i+1] ,中序元素i[:i],与右子树元素前序元素p[i+1:] ,中序元素i[i+1:],直到p中没有元素为止

• 时间复杂度(O(n))
• 空间复杂度(O(n))

执行结果

中序递归添加

func buildTree(preorder []int, inorder []int) *TreeNode {
 if len(preorder) == 0 {
  return nil
 }
 i := 0
 for ; i < len(inorder); i++ {
  if inorder[i] == preorder[0] {
   break
  }
 }
 r := TreeNode{preorder[0], nil, nil}
 r.Left = buildTree(preorder[1:i+1], inorder[:i])
 r.Right = buildTree(preorder[i+1:], inorder[i+1:])
 return &r
}

执行用时： 4 ms , 在所有 Go 提交中击败了 91.41% 的用户 内存消耗： 3.9 MB , 在所有 Go 提交中击败了 89.40% 的用户 通过测试用例： 203 / 203