网易首页 > 网易号 > 正文 申请入驻

文心一言 VS 讯飞星火 VS chatgpt (144)-- 算法导论12.1 4题

0
分享至

四、用go语言,对于一棵有 n 个结点的树,请设计在 O(n)时间内完成的先序遍历算法和后序遍历算法。

我个人喜欢灵小智。

文心一言:

在 Go 语言中,我们可以使用递归来实现树的前序遍历和后序遍历。以下是实现这两种方法的代码。

首先,我们定义一个树节点的结构:

typeTreeNodestruct{
Valint
Left*TreeNode
Right*TreeNode
}

接下来,我们实现前序遍历(根-左-右):

funcpreOrderTraversal(root*TreeNode){
ifroot==nil{//空节点则返回
return
}
fmt.Println(root.Val)//先打印根节点
preOrderTraversal(root.Left)//然后遍历左子树
preOrderTraversal(root.Right)//最后遍历右子树
}

然后,我们实现后序遍历(左-右-根):

funcpostOrderTraversal(root*TreeNode){
ifroot==nil{//空节点则返回
return
}
postOrderTraversal(root.Left)//先遍历左子树
postOrderTraversal(root.Right)//然后遍历右子树
fmt.Println(root.Val)//最后打印根节点
}

以上的前序遍历和后序遍历的时间复杂度都是 O(n),其中 n 是树的节点数量。这是因为每个节点都会被访问一次,每个节点只会被访问一次。

讯飞星火,代码正常运行:

packagemain
import"fmt"
typeTreeNodestruct{
Valint
Left*TreeNode
Right*TreeNode
}
funcpreorderTraversal(root*TreeNode)[]int{
ifroot==nil{
return[]int{}
}
stack:=[]*TreeNode{root}
res:=[]int{root.Val}
forlen(stack)>0{
node:=stack[len(stack)-1]
stack=stack[:len(stack)-1]
ifnode.Right!=nil{
stack=append(stack,node.Right)
res=append(res,node.Right.Val)
}
ifnode.Left!=nil{
stack=append(stack,node.Left)
res=append(res,node.Left.Val)
}
}
returnres
}
funcpostorderTraversal(root*TreeNode)[]int{
ifroot==nil{
return[]int{}
}
stack:=[]*TreeNode{root}
res:=[]int{}
forlen(stack)>0{
node:=stack[len(stack)-1]
stack=stack[:len(stack)-1]
res=append(res,node.Val)
ifnode.Left!=nil{
stack=append(stack,node.Left)
}
ifnode.Right!=nil{
stack=append(stack,node.Right)
}
}
fori,n:=0,len(res);ires[i],res[n-1-i]=res[n-1-i],res[i]
}
returnres
}
funcmain(){
root:=&TreeNode{Val:1}
root.Left=&TreeNode{Val:2}
root.Right=&TreeNode{Val:3}
root.Left.Left=&TreeNode{Val:4}
root.Left.Right=&TreeNode{Val:5}
root.Right.Left=&TreeNode{Val:6}
root.Right.Right=&TreeNode{Val:7}
fmt.Println("先序遍历结果:",preorderTraversal(root))
fmt.Println("后序遍历结果:",postorderTraversal(root))
}

360智脑,代码不能运行:

以下是用go语言实现一棵有 n 个结点的树的先序遍历和后序遍历算法:

先序遍历算法:

packagemain
import"fmt"
funcpreOrder(node*Node)[]int{
res:=[]int{}
ifnode!=nil{
res=append(res,node.val)
preOrder(node.left)
preOrder(node.right)
}
returnres
}
funcmain(){
//创建一棵有3个结点的二叉树
root:=&Node{val:10,left:nil,right:nil}
root.left=&Node{val:5,left:nil,right:&Node{}}
root.left.left=&Node{val:3,left:nil,right:nil}
root.left.right=&Node{val:7,left:nil,right:nil}
root.right=&Node{val:15,left:nil,right:&Node{}}
root.right.left=&Node{val:2,left:nil,right:nil}
root.right.right=&Node{val:12,left:nil,right:nil}
//输出先序遍历结果
res:=preOrder(root)
fmt.Println(res)//输出[105721215]
}

后序遍历算法:

packagemain
import"fmt"
funcpostOrder(node*Node)[]int{
res:=[]int{}
ifnode!=nil{
res=append(res,node.val)
postOrder(node.left)
postOrder(node.right)
}
returnres
}
funcmain(){
//创建一棵有3个结点的二叉树
root:=&Node{val:10,left:nil,right:nil}
root.left=&Node{val:5,left:nil,right:nil}
root.left.left=&Node{val:3,left:nil,right:nil}
root.left.right=&Node{val:7,left:nil,right:nil}
root.right=&Node{val:15,left:nil,right:nil}
root.right.left=&Node{val:2,left:nil,right:nil}
root.right.right=&Node{val:12,left:nil,right:nil}
//输出后序遍历结果
res:=postOrder(root)
fmt.Println(res)//输出[152127105315]
}

智谱清言:

在 Go 语言中,可以使用递归或迭代方法实现树的遍历。以下是先序遍历和后序遍历的递归和迭代算法:

1.先序遍历算法:

递归算法:

funcpreOrderTraversalRecursive(root*TreeNode)[]int{
ifroot==nil{
return[]int{}
}
result:=[]int{root.Val}
result=append(result,preOrderTraversalRecursive(root.Left)...)
result=append(result,preOrderTraversalRecursive(root.Right)...)
returnresult
}

迭代算法:

funcpreOrderTraversalIterative(root*TreeNode)[]int{
ifroot==nil{
return[]int{}
}
result:=[]int{}
stack:=[]*TreeNode{root}
forlen(stack)>0{
node:=stack[len(stack)-1]
stack=stack[:len(stack)-1]
result=append(result,node.Val)
ifnode.Right!=nil{
stack=append(stack,node.Right)
}
ifnode.Left!=nil{
stack=append(stack,node.Left)
}
}
returnresult
}

2.后序遍历算法:

递归算法:

funcpostOrderTraversalRecursive(root*TreeNode)[]int{
ifroot==nil{
return[]int{}
}
result:=postOrderTraversalRecursive(root.Left)
result=append(result,root.Val)
result=append(result,postOrderTraversalRecursive(root.Right)...)
returnresult
}

迭代算法:

funcpostOrderTraversalIterative(root*TreeNode)[]int{
ifroot==nil{
return[]int{}
}
result:=[]int{}
stack:=[]*TreeNode{root}
forlen(stack)>0{
node:=stack[len(stack)-1]
stack=stack[:len(stack)-1]
result=append(result,node.Val)
ifnode.Left!=nil{
stack=append(stack,node.Left)
}
ifnode.Right!=nil{
stack=append(stack,node.Right)
}
}
//Reversetheresultarraytogetpost-ordertraversal
fori,j:=0,len(result)-1;iresult[i],result[j]=result[j],result[i]
}
returnresult
}

以上算法均能在 O(n) 时间内完成树的遍历。

通义千问:

这是一个经典的二叉树问题,我们可以使用深度优先搜索(DFS)来解决这个问题。

首先,我们需要定义一个树节点的数据结构:

typeTreeNodestruct{
Valint
Left*TreeNode
Right*TreeNode
}

然后,我们分别实现先序遍历和后序遍历的函数:

先序遍历:根 -> 左 -> 右

funcpreorderTraversal(root*TreeNode)[]int{
ifroot==nil{
return[]int{}
}
result:=make([]int,0)
stack:=[]*TreeNode{root}
forlen(stack)>0{
node:=stack[len(stack)-1]
result=append(result,node.Val)
ifnode.Right!=nil{
stack=append(stack,node.Right)
}
ifnode.Left!=nil{
stack=append(stack,node.Left)
}else{
stack=stack[:len(stack)-1]
}
}
returnresult
}

后序遍历:左 -> 右 -> 根

funcpostorderTraversal(root*TreeNode)[]int{
ifroot==nil{
return[]int{}
}
result:=make([]int,0)
stack:=[]*TreeNode{root}
prev:=root
forlen(stack)>0{
node:=stack[len(stack)-1]
ifnode.Left==nil&&node.Right==nil||node==prev{
result=append([]int{node.Val},result...)
prev=node
stack=stack[:len(stack)-1]
}elseifnode.Right!=nil{
stack=append(stack,node.Right)
}else{
stack=stack[:len(stack)-1]
ifnode.Left!=nil{
stack=append(stack,node.Left)
}
}
}
returnresult
}

这两种方法的时间复杂度都是O(n),其中n是树中节点的数量,因为我们只需要遍历一次所有的节点。空间复杂度也是O(n),因为在最坏的情况下,我们可能需要将所有的节点都压入栈中。

天工:

先序遍历算法:

先序遍历是指先访问根节点,然后依次访问左子树和右子树。在 Go 语言中,可以使用递归实现先序遍历算法。具体实现如下:

//定义一个树节点结构体
typeTreeNodestruct{
Valint
Left*TreeNode
Right*TreeNode
}
//先序遍历算法
funcPreorderTraversal(root*TreeNode){
ifroot==nil{
return
}
//访问当前节点
fmt.Printf("%d",root.Val)
//递归访问左右子树
PreorderTraversal(root.Left)
PreorderTraversal(root.Right)
}

后序遍历算法:

后序遍历是指先访问左子树,然后访问右子树,最后访问根节点。在 Go 语言中,可以使用递归实现后序遍历算法。具体实现如下:

//定义一个树节点结构体
typeTreeNodestruct{
Valint
Left*TreeNode
Right*TreeNode
}
//后序遍历算法
funcPostorderTraversal(root*TreeNode){
ifroot==nil{
return
}
//递归访问左右子树
PostorderTraversal(root.Left)
PostorderTraversal(root.Right)
//访问当前节点
fmt.Printf("%d",root.Val)
}

以上两个算法都是使用递归实现的,时间复杂度为 O(n),空间复杂度为 O(h),其中 h 是树的高度。

灵小智,代码正常运行:

在Go语言中,可以使用递归的方式实现树的先序遍历和后序遍历算法。下面是相应的实现:

packagemain
import"fmt"
//树的节点结构定义
typeTreeNodestruct{
Valint
Children[]*TreeNode
}
//先序遍历函数
funcPreorderTraversal(root*TreeNode){
ifroot==nil{
return
}
fmt.Printf("%d",root.Val)//先输出当前节点的值
for_,child:=rangeroot.Children{
PreorderTraversal(child)//递归遍历子节点
}
}
//后序遍历函数
funcPostorderTraversal(root*TreeNode){
ifroot==nil{
return
}
for_,child:=rangeroot.Children{
PostorderTraversal(child)//递归遍历子节点
}
fmt.Printf("%d",root.Val)//最后输出当前节点的值
}
funcmain(){
//构建一个示例树
root:=&TreeNode{Val:1}
node2:=&TreeNode{Val:2}
node3:=&TreeNode{Val:3}
node4:=&TreeNode{Val:4}
node5:=&TreeNode{Val:5}
root.Children=[]*TreeNode{node2,node3,node4}
node2.Children=[]*TreeNode{node5}
//先序遍历
fmt.Println("PreorderTraversal:")
PreorderTraversal(root)
fmt.Println()
//后序遍历
fmt.Println("PostorderTraversal:")
PostorderTraversal(root)
fmt.Println()
}

以上代码通过先序遍历和后序遍历的方式遍历了一棵示例树,并输出了遍历结果。请注意,这里的先序遍历和后序遍历算法的时间复杂度为 O(n),其中 n 是树中节点的个数。

chatgpt,代码正常运行:

在Go语言中,可以使用迭代的方式来实现树的先序遍历和后序遍历,以保证时间复杂度为O(n)。以下是示例代码:

packagemain
import(
"fmt"
)
//树节点结构体
typeNodestruct{
Valueint
Left*Node
Right*Node
}
//先序遍历
funcPreorderTraversal(root*Node){
ifroot==nil{
return
}
stack:=[]*Node{root}
forlen(stack)>0{
node:=stack[len(stack)-1]
stack=stack[:len(stack)-1]
fmt.Printf("%d",node.Value)
ifnode.Right!=nil{
stack=append(stack,node.Right)
}
ifnode.Left!=nil{
stack=append(stack,node.Left)
}
}
}
//后序遍历
funcPostorderTraversal(root*Node){
ifroot==nil{
return
}
stack1:=[]*Node{root}
stack2:=[]*Node{}
forlen(stack1)>0{
node:=stack1[len(stack1)-1]
stack1=stack1[:len(stack1)-1]
stack2=append(stack2,node)
//左子树先入栈
ifnode.Left!=nil{
stack1=append(stack1,node.Left)
}
//右子树后入栈
ifnode.Right!=nil{
stack1=append(stack1,node.Right)
}
}
fori:=len(stack2)-1;i>=0;i--{
fmt.Printf("%d",stack2[i].Value)
}
}
funcmain(){
//构建一棵树作为示例
root:=&Node{
Value:1,
Left:&Node{
Value:2,
Left:&Node{
Value:4,
Left:nil,
Right:nil,
},
Right:&Node{
Value:5,
Left:nil,
Right:nil,
},
},
Right:&Node{
Value:3,
Left:&Node{
Value:6,
Left:nil,
Right:nil,
},
Right:nil,
},
}
fmt.Println("先序遍历结果:")
PreorderTraversal(root)
fmt.Println("\n后序遍历结果:")
PostorderTraversal(root)
}

以上代码中,我们使用了两个栈来实现后序遍历。第一个栈用于模拟先序遍历,将右子节点先入栈,然后左子节点入栈。第二个栈用于保存逆向的结果,在第一个栈为空时,将第一个栈中的元素依次弹出并加入到第二个栈中,然后输出即为后序遍历结果。

声明:内容由AI生成

特别声明:以上内容(如有图片或视频亦包括在内)为自媒体平台“网易号”用户上传并发布,本平台仅提供信息存储服务。

Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.

相关推荐
热点推荐
92分钟绝杀,2-1大冷门,倒数第2逆转北京国安,一夜逃离降级区

92分钟绝杀,2-1大冷门,倒数第2逆转北京国安,一夜逃离降级区

侧身凌空斩
2024-06-15 22:07:12
遭逆转送温暖!国安球迷冲官博评论区,怒斥主帅苏亚雷斯

遭逆转送温暖!国安球迷冲官博评论区,怒斥主帅苏亚雷斯

直播吧
2024-06-15 22:46:20
女生主动起来会有多主动?网友:已四十,在星巴克打排位被要微信

女生主动起来会有多主动?网友:已四十,在星巴克打排位被要微信

奇特短尾矮袋鼠
2024-06-14 12:29:40
南京市市管领导干部任前公示通告

南京市市管领导干部任前公示通告

鲁中晨报
2024-06-15 21:35:07
国家大基金重点投资了这9家半导体企业,都是低位低估值优质资产

国家大基金重点投资了这9家半导体企业,都是低位低估值优质资产

小蜜情感说
2024-06-15 06:02:04
森林北前夫照片曝光,谁能想到是他啊?

森林北前夫照片曝光,谁能想到是他啊?

银河卧谈会
2024-06-13 15:08:19
儿媳照顾50岁农村公公,酒后公公行夫妻之事,公公:儿媳经验丰富

儿媳照顾50岁农村公公,酒后公公行夫妻之事,公公:儿媳经验丰富

魅老八足球
2024-05-13 13:49:37
匈牙利也扛不住了?北约秘书长高调宣布:北约全票通过对乌军援

匈牙利也扛不住了?北约秘书长高调宣布:北约全票通过对乌军援

环球Talk
2024-06-15 23:48:51
罕见省部级高干在中央党报公开表达“不满”:困惑很久,不吐不快

罕见省部级高干在中央党报公开表达“不满”:困惑很久,不吐不快

华人星光
2024-06-07 19:20:09
全球驱逐舰排名前十:日本1艘,韩国第4,中国排名意外,差距悬殊

全球驱逐舰排名前十:日本1艘,韩国第4,中国排名意外,差距悬殊

文雅笔墨
2024-06-15 13:12:47
16岁338天,亚马尔打破欧洲杯历史最年轻出场纪录

16岁338天,亚马尔打破欧洲杯历史最年轻出场纪录

懂球帝
2024-06-15 22:47:15
欧盟将对中国电动汽车开征额外关税 比亚迪减半 特斯拉享“优待”

欧盟将对中国电动汽车开征额外关税 比亚迪减半 特斯拉享“优待”

瑶看新车
2024-06-13 16:44:45
确定加盟,恭喜AC米兰,2000万,达成协议,国米有对手了

确定加盟,恭喜AC米兰,2000万,达成协议,国米有对手了

开心体育站
2024-06-15 23:37:30
河南三门峡市陕州区甘山林场原场长刘正理接受审查调查

河南三门峡市陕州区甘山林场原场长刘正理接受审查调查

鲁中晨报
2024-06-15 10:59:02
苹果Vision Pro国内正式开启预售:美国火爆、中国冷清 3万元高昂定价谁来买单?

苹果Vision Pro国内正式开启预售:美国火爆、中国冷清 3万元高昂定价谁来买单?

每日经济新闻
2024-06-14 11:48:04
妻子陪初恋男友法国游玩,下飞机才通知丈夫,返回后直接愣在机场

妻子陪初恋男友法国游玩,下飞机才通知丈夫,返回后直接愣在机场

局内人
2024-05-15 14:12:33
中国从未封禁比特币挖矿?分析师:境内活动基本恢复 助力实现2060年碳中和

中国从未封禁比特币挖矿?分析师:境内活动基本恢复 助力实现2060年碳中和

FX168链界观察
2024-06-14 17:21:23
妻子为男闺蜜当众泼我一杯酒,1天后她道歉,我直言:晚了

妻子为男闺蜜当众泼我一杯酒,1天后她道歉,我直言:晚了

吉祥情感屋
2024-06-12 11:28:14
老戏骨离世!66岁抗癌失败,演员妻子忙着拍戏,最后一面都没见到

老戏骨离世!66岁抗癌失败,演员妻子忙着拍戏,最后一面都没见到

综艺拼盘汇
2024-06-15 04:27:27
老百姓傻眼了?全国铁饭碗人数加起来都不到一个亿!

老百姓傻眼了?全国铁饭碗人数加起来都不到一个亿!

娱乐洞察点点
2024-06-15 16:37:29
2024-06-16 02:14:44
moonfdd
moonfdd
福大大架构师每日一题
423文章数 7关注度
往期回顾 全部

科技要闻

TikTok开始找退路了?

头条要闻

563支AI队伍和姜萍考同一份试卷:最高34分 都没进决赛

头条要闻

563支AI队伍和姜萍考同一份试卷:最高34分 都没进决赛

体育要闻

莱夫利,让困难为我让路

娱乐要闻

江宏杰秀儿女刺青,不怕刺激福原爱?

财经要闻

新情况!高层对人民币的态度180°转弯

汽车要闻

东风奕派eπ008售21.66万元 冰箱彩电都配齐

态度原创

艺术
游戏
时尚
本地
军事航空

艺术要闻

穿越时空的艺术:《马可·波罗》AI沉浸影片探索人类文明

魂师对决:SP唐昊返场抽取价值分析!真身幻金真是一个都少不了!

艳压四方的刘亦菲,也没能赢她

本地新闻

粽情一夏|海河龙舟赛,竟然成了外国人的大party!

军事要闻

普京提停火和谈条件 美防长迅速回应

无障碍浏览 进入关怀版