j
jaryue
V1
2023/04/09阅读:16主题:默认主题
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
作者介绍
j
jaryue
V1