程序地带

剑指 Offer 07. 重建二叉树 (golang版)


思路: 1.前序遍历的第一个节点是二叉树的根节点 2.中序遍历中,根节点左边是左子树,右边是右子树 3.理清思绪递归实现即可
func buildTree(preorder []int, inorder []int) *TreeNode {
//结束条件,最下面的叶子节点时结束
if len(preorder) == 0 {
return nil
}
//根据前序遍历的性质在中序遍历中找到根节点的位置
var i = 0
for i < len(preorder) && preorder[0] != inorder[i] {
i++
}
//递归左子树
l := buildTree(preorder[1:i+1], inorder[:i])
//递归右子树
r := buildTree(preorder[i+1:], inorder[i+1:])
return &TreeNode{
Val: preorder[0],
Left: l,
Right: r,
}
}
测试代码:
package main
import "fmt"
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
func main() {
//var preorder = []int{3,9,20,15,7}
//var inorder = []int {9,3,15,20,7}
var preorder = []int{1,2,4,8,5,9,3,6,7,10}
var inorder = []int{4,8,2,9,5,1,6,3,7,10}
root := buildTree(preorder,inorder)
//前序遍历
//printVLRTree(root)
//中序遍历
//printLDRTree(root)
//后序遍历
printLRDTree(root)
}
func buildTree(preorder []int, inorder []int) *TreeNode {
if len(preorder) == 0 {
return nil
}
var i = 0
for i < len(preorder) && preorder[0] != inorder[i] {
i++
}
//fmt.Println(preorder,inorder,i)
l := buildTree(preorder[1:i+1], inorder[:i])
r := buildTree(preorder[i+1:], inorder[i+1:])
return &TreeNode{
Val: preorder[0],
Left: l,
Right: r,
}
}
//前序遍历
func printVLRTree(root *TreeNode){
if root == nil {
return
}
fmt.Println(root.Val)
printVLRTree(root.Left)
printVLRTree(root.Right)
}
//中序遍历
func printLDRTree(root *TreeNode){
if root == nil {
return
}
printLDRTree(root.Left)
fmt.Println(root.Val)
printLDRTree(root.Right)
}
//后序遍历
func printLRDTree(root *TreeNode){
if root == nil {
return
}
printLRDTree(root.Left)
printLRDTree(root.Right)
fmt.Println(root.Val)
}

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/admin_o1/article/details/111246025

随机推荐

7月30日 举办专注于微服务的.NET Conf Focus

7月30日 举办专注于微服务的.NET Conf Focus

2020年7月30日,由.NET基金会和微软将举办一个在线和为期一天的活动,包括微软.NET团队的演讲者以及社区的演讲者。本次在线大会专注.NET框架构建微服务,演讲者分享构建和部署云原生应用程序的最...

张善友 阅读(436)

配置文件初始化异常Configuration system failed to initialize

最近用户反映一些电脑启动程序就崩溃,还给演示了一个比较诡异的问题“把软件重新拷贝到另外一个目录,就能正常运行"。还说过一段时间又不能运行需要在换个位置。’由于当时没有设置全局异常,只能借助系...

ColorsWin 阅读(991)

netty 线程模型

netty 线程模型

Netty是Java领域有名的开源网络库,特点是高性能和高扩展性,因此很多流行的框架都是基于它来构建的,比如我们熟知的Dubbo、Rocketmq、Hadoo...

寻烟的衣袖 阅读(379)

分享一个最最基本实用的开发流程

分享一个最最基本实用的开发流程

「开发流程」在不同的产品项目中,不同规模的企业中,往往也不尽相同,有瀑布、有敏捷,但最基本的开发流程理当如图所示,也是最简单最容易实操,公认度最高如果实践这套流程,说明你们在甲方爸爸面前比较硬气的那种...

那是山 阅读(721)

.NetCore学习笔记:六、Swagger API接口文档工具

.NetCore学习笔记:六、Swagger API接口文档工具

Swagger一个优秀的Api接口文档生成工具。Swagger可以可以动态生成Api接口文档,有效的降低前后端人员关于Api接口的沟通成本,促进项目高效开发。1、使用NuGet安装最新的包:Swash...

爱听民谣的程序猿 阅读(122)

ORACLE常用操作

一、表空间相关1、查看所有的表空间:SELECT*FROM DBA_TABLESPACES;2、查看某个用户的默认表空间:SELECTDEFAULT_TABLESPACE,...

树獭不是树懒 阅读(240)

C#拆分中文和数字字符串

比如要拆分“呵呵呵90909086676喝喝999”,下面当type=0返回的是中文字符串“呵呵呵,喝喝”,type=1返回的是数字字符串“90909086676,999”,privatestring...

舒碧 阅读(602)

Spring简单入门案例依赖概念基础

springIoc入门案例创建一个mavenJava工程  引入依赖<dependencies>       <dependency>           <groupI...

时光机jay 阅读(910)