遍历构造python二叉树的示例分析
发表于:2024-11-22 作者:千家信息网编辑
千家信息网最后更新 2024年11月22日,今天就跟大家聊聊有关遍历构造python二叉树的示例分析,可能很多人都不太了解,为了让大家更加了解,小编给大家总结了以下内容,希望大家根据这篇文章可以有所收获。根据一棵树的前序遍历与中序遍历构造二叉树
千家信息网最后更新 2024年11月22日遍历构造python二叉树的示例分析
今天就跟大家聊聊有关遍历构造python二叉树的示例分析,可能很多人都不太了解,为了让大家更加了解,小编给大家总结了以下内容,希望大家根据这篇文章可以有所收获。
根据一棵树的前序遍历与中序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
例如,给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树:
3
/ \
9 20
/ \
15 7
解题思路:
1,前序遍历的话第一个一定是根
2,中序遍历的话和根元素相等的元素左边一定在左子树,设根元素位置为i
3,前序遍历,前长度为i+1的元素一定在左子树
4,递归求解
/**
* 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) < 1 || len(inorder) < 1 {
return nil
}
if len(preorder) == 1 {
return &TreeNode{
Val: preorder[0],
}
}
if len(inorder) == 1 {
return &TreeNode{
Val: inorder[0],
}
}
i := 0
for ; i < len(inorder); i++ {
if preorder[0] == inorder[i] {
break
}
}
if i == len(inorder) {
return nil
}
h := &TreeNode{
Val: preorder[0],
}
if i == 0 {
h.Right = buildTree(preorder[1:], inorder[i+1:])
} else if i == len(inorder)-1 {
h.Left = buildTree(preorder[1:], inorder[:i])
} else {
h.Left = buildTree(preorder[1:i+1], inorder[:i])
h.Right = buildTree(preorder[i+1:], inorder[i+1:])
}
return h
}
根据一棵树的中序遍历与后序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
例如,给出
中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]
返回如下的二叉树:
3
/ \
9 20
/ \
15 7
解题思路:
1,后序遍历的话最后一个一定是根
2,中序遍历的话和根元素相等的元素左边一定在左子树,设根元素位置为i
3,后序遍历,前长度为i+1的元素一定在左子树
4,递归求解
/** * 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)<1 ||len(postorder)<1{ return nil } if len(inorder)==1{ return &TreeNode{Val:inorder[0]} } i:=0 for ;i
看完上述内容,你们对遍历构造python二叉树的示例分析有进一步的了解吗?如果还想了解更多知识或者相关内容,请关注行业资讯频道,感谢大家的支持。
元素
子树
内容
示例
分析
位置
思路
长度
一棵树
递归
更多
知识
篇文章
行业
资讯
资讯频道
频道
进一
支持
有关
数据库的安全要保护哪些东西
数据库安全各自的含义是什么
生产安全数据库录入
数据库的安全性及管理
数据库安全策略包含哪些
海淀数据库安全审计系统
建立农村房屋安全信息数据库
易用的数据库客户端支持安全管理
连接数据库失败ssl安全错误
数据库的锁怎样保障安全
悦网网络技术有限公司怎么样
绍兴橙猫网络技术有限公司
分销系统软件开发
日本知名的软件开发公司
如何删除数据库表项
dayz丧尸末日数据库打开
海南大学生网络安全保卫
郑州速点网络技术有限公司
家庭网络安全事件
计算机网络技术和影视的关系
互联网金融软件开发与应用-
数据库实例表空间
强制解绑显示服务器在忙
数据库子类超类
中华人民共和国网络安全工作责任
分布式数据库如何容灾
华数 服务器
项立刚谈网络技术
网络安全保护的义务是什么
数据库模型的内存怎么用
润和软件 网络安全
深圳共进电子软件开发怎么样
软件开发推广视频
网络安全日常生活应用
putty重启服务器
福建 网络安全 人才
阿里云ibm服务器
聚才网络技术有限公司招聘
淘宝的服务器
网络安全的征文四百字