内容简介:根据一棵树的前序遍历与中序遍历构造二叉树你可以假设树中没有重复的元素。例如,给出
描述
根据一棵树的前序遍历与中序遍历构造二叉树
注意:
你可以假设树中没有重复的元素。
例如,给出
前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树:
3 / \ 9 20 / \ 15 7
思路
- 前序遍历中,第一个节点即根节点
- 在中序遍历中,找出第一个节点的位置,根节点前面的 L 个数据,即根节点左子树的中序遍历数据,前序遍历中根节点后面的 L 个数据即左子树的前序遍历
- 右子树同上
- 简而言之,确定了根节点,确定了左子树和右子树的数据,递归对左子树和右子树进行重建
代码实现
// 根据一棵树的前序遍历与中序遍历构造二叉树 // TreeNode Definition for a binary tree node. type TreeNode struct { Val int Left *TreeNode Right *TreeNode } func buildTree(preorder []int, inorder []int) *TreeNode { if len(preorder) == 0 { return nil } //前序遍历的第一个节点即根节点 res := &TreeNode{ Val: preorder[0], } if len(preorder) == 1 { return res } // 在中序遍历中,根节点前面的即根节点的左子树,后面的即右子树 //匿名函数 idx := func(val int, nums []int) int { for i, v := range nums { if v == val { return i } } return -1 }(res.Val, inorder) if idx == -1 { panic("data error") } //递归,构建根节点左子树和右子树 res.Left = buildTree(preorder[1:idx+1], inorder[:idx]) res.Right = buildTree(preorder[idx+1:], inorder[idx+1:]) return res }
题目来源
GitHub
- 源码传送门
- 各种数据结构及算法实现, LeetCode解题思路及答案
- 大厂面试题汇总及答案解析
本文为原创文章,转载注明出处,欢迎扫码关注公众号 楼兰
或者网站 https://lovecoding.club
,第一时间看后续精彩文章,觉得好的话,顺手分享到朋友圈吧,感谢支持。
以上所述就是小编给大家介绍的《LeetCode105. 从前序与中序遍历序列构造二叉树》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:- 力扣(105):从前序与中序遍历序列构造二叉树
- 【Leetcode】105. 从前序与中序遍历序列构造二叉树
- 【Leetcode】106. 从中序与后序遍历序列构造二叉树2
- 数组常见的遍历循环方法、数组的循环遍历的效率对比
- C++拾趣——STL容器的插入、删除、遍历和查找操作性能对比(Windows VirtualStudio)——遍历和删除
- Js遍历数组总结
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。