文心一言 VS 讯飞星火 VS chatgpt （144）-- 算法导论12.1 4题
四、用go语言，对于一棵有 n 个结点的树，请设计在 O(n)时间内完成的先序遍历算法和后序遍历算法。
我个人喜欢?灵小智?。
文心一言：
在 Go 语言中，我们可以使用递归来实现树的前序遍历和后序遍历。以下是实现这两种方法的代码。
首先，我们定义一个树节点的结构：
type?TreeNode?struct?{
Val???int
Left??*TreeNode
Right?*TreeNode
}
接下来，我们实现前序遍历（根-左-右）：
func?preOrderTraversal(root?*TreeNode)?{
if?root?==?nil?{?//?空节点则返回
return
}
fmt.Println(root.Val)?//?先打印根节点
preOrderTraversal(root.Left)?//?然后遍历左子树
preOrderTraversal(root.Right)?//?最后遍历右子树
}
然后，我们实现后序遍历（左-右-根）：
func?postOrderTraversal(root?*TreeNode)?{
if?root?==?nil?{?//?空节点则返回
return
}
postOrderTraversal(root.Left)?//?先遍历左子树
postOrderTraversal(root.Right)?//?然后遍历右子树
fmt.Println(root.Val)?//?最后打印根节点
}
以上的前序遍历和后序遍历的时间复杂度都是 O(n)，其中 n 是树的节点数量。这是因为每个节点都会被访问一次，每个节点只会被访问一次。
在这里插入图片描述
在这里插入图片描述讯飞星火，代码正常运行：
package?main
import?"fmt"
type?TreeNode?struct?{
Val???int
Left??*TreeNode
Right?*TreeNode
}
func?preorderTraversal(root?*TreeNode)?[]int?{
if?root?==?nil?{
return?[]int{}
}
stack?:=?[]*TreeNode{root}
res?:=?[]int{root.Val}
for?len(stack)?>?0?{
node?:=?stack[len(stack)-1]
stack?=?stack[:len(stack)-1]
if?node.Right?!=?nil?{
stack?=?append(stack,?node.Right)
res?=?append(res,?node.Right.Val)
}
if?node.Left?!=?nil?{
stack?=?append(stack,?node.Left)
res?=?append(res,?node.Left.Val)
}
}
return?res
}
func?postorderTraversal(root?*TreeNode)?[]int?{
if?root?==?nil?{
return?[]int{}
}
stack?:=?[]*TreeNode{root}
res?:=?[]int{}
for?len(stack)?>?0?{
node?:=?stack[len(stack)-1]
stack?=?stack[:len(stack)-1]
res?=?append(res,?node.Val)
if?node.Left?!=?nil?{
stack?=?append(stack,?node.Left)
}
if?node.Right?!=?nil?{
stack?=?append(stack,?node.Right)
}
}
for?i,?n?:=?0,?len(res);?i?
res[i],?res[n-1-i]?=?res[n-1-i],?res[i]
}
return?res
}
func?main()?{
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 个结点的树的先序遍历和后序遍历算法：
先序遍历算法：
package?main
import?"fmt"
func?preOrder(node?*Node)?[]int?{
res?:=?[]int{}
if?node?!=?nil?{
res?=?append(res,?node.val)
preOrder(node.left)
preOrder(node.right)
}
return?res
}
func?main()?{
//?创建一棵有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)?//?输出?[10?5?7?2?12?15]
}
后序遍历算法：
package?main
import?"fmt"
func?postOrder(node?*Node)?[]int?{
res?:=?[]int{}
if?node?!=?nil?{
res?=?append(res,?node.val)
postOrder(node.left)
postOrder(node.right)
}
return?res
}
func?main()?{
//?创建一棵有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)?//?输出?[15?2?12?7?10?5?3?15]
}
在这里插入图片描述
在这里插入图片描述智谱清言：
在 Go 语言中，可以使用递归或迭代方法实现树的遍历。以下是先序遍历和后序遍历的递归和迭代算法：
1.先序遍历算法：
递归算法：
func?preOrderTraversalRecursive(root?*TreeNode)?[]int?{
if?root?==?nil?{
return?[]int{}
}
result?:=?[]int{root.Val}
result?=?append(result,?preOrderTraversalRecursive(root.Left)...)
result?=?append(result,?preOrderTraversalRecursive(root.Right)...)
return?result
}
迭代算法：
func?preOrderTraversalIterative(root?*TreeNode)?[]int?{
if?root?==?nil?{
return?[]int{}
}
result?:=?[]int{}
stack?:=?[]*TreeNode{root}
for?len(stack)?>?0?{
node?:=?stack[len(stack)-1]
stack?=?stack[:len(stack)-1]
result?=?append(result,?node.Val)
if?node.Right?!=?nil?{
stack?=?append(stack,?node.Right)
}
if?node.Left?!=?nil?{
stack?=?append(stack,?node.Left)
}
}
return?result
}
2.后序遍历算法：
递归算法：
func?postOrderTraversalRecursive(root?*TreeNode)?[]int?{
if?root?==?nil?{
return?[]int{}
}
result?:=?postOrderTraversalRecursive(root.Left)
result?=?append(result,?root.Val)
result?=?append(result,?postOrderTraversalRecursive(root.Right)...)
return?result
}
迭代算法：
func?postOrderTraversalIterative(root?*TreeNode)?[]int?{
if?root?==?nil?{
return?[]int{}
}
result?:=?[]int{}
stack?:=?[]*TreeNode{root}
for?len(stack)?>?0?{
node?:=?stack[len(stack)-1]
stack?=?stack[:len(stack)-1]
result?=?append(result,?node.Val)
if?node.Left?!=?nil?{
stack?=?append(stack,?node.Left)
}
if?node.Right?!=?nil?{
stack?=?append(stack,?node.Right)
}
}
//?Reverse?the?result?array?to?get?post-order?traversal
for?i,?j?:=?0,?len(result)-1;?i?
result[i],?result[j]?=?result[j],?result[i]
}
return?result
}
以上算法均能在 O(n) 时间内完成树的遍历。
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述通义千问：
这是一个经典的二叉树问题，我们可以使用深度优先搜索（DFS）来解决这个问题。
首先，我们需要定义一个树节点的数据结构：
type?TreeNode?struct?{
Val?int
Left?*TreeNode
Right?*TreeNode
}
然后，我们分别实现先序遍历和后序遍历的函数：
先序遍历：根 -> 左 -> 右
func?preorderTraversal(root?*TreeNode)?[]int?{
if?root?==?nil?{
return?[]int{}
}
result?:=?make([]int,?0)
stack?:=?[]*TreeNode{root}
for?len(stack)?>?0?{
node?:=?stack[len(stack)-1]
result?=?append(result,?node.Val)
if?node.Right?!=?nil?{
stack?=?append(stack,?node.Right)
}
if?node.Left?!=?nil?{
stack?=?append(stack,?node.Left)
}?else?{
stack?=?stack[:len(stack)-1]
}
}
return?result
}
后序遍历：左 -> 右 -> 根
func?postorderTraversal(root?*TreeNode)?[]int?{
if?root?==?nil?{
return?[]int{}
}
result?:=?make([]int,?0)
stack?:=?[]*TreeNode{root}
prev?:=?root
for?len(stack)?>?0?{
node?:=?stack[len(stack)-1]
if?node.Left?==?nil?&&?node.Right?==?nil?||?node?==?prev?{
result?=?append([]int{node.Val},?result...)
prev?=?node
stack?=?stack[:len(stack)-1]
}?else?if?node.Right?!=?nil?{
stack?=?append(stack,?node.Right)
}?else?{
stack?=?stack[:len(stack)-1]
if?node.Left?!=?nil?{
stack?=?append(stack,?node.Left)
}
}
}
return?result
}
这两种方法的时间复杂度都是O(n)，其中n是树中节点的数量，因为我们只需要遍历一次所有的节点。空间复杂度也是O(n)，因为在最坏的情况下，我们可能需要将所有的节点都压入栈中。
在这里插入图片描述
在这里插入图片描述在这里插入图片描述天工：
先序遍历算法：
先序遍历是指先访问根节点，然后依次访问左子树和右子树。在 Go 语言中，可以使用递归实现先序遍历算法。具体实现如下：
//?定义一个树节点结构体
type?TreeNode?struct?{
Val?int
Left?*TreeNode
Right?*TreeNode
}
//?先序遍历算法
func?PreorderTraversal(root?*TreeNode)?{
if?root?==?nil?{
return
}
//?访问当前节点
fmt.Printf("%d?",?root.Val)
//?递归访问左右子树
PreorderTraversal(root.Left)
PreorderTraversal(root.Right)
}
后序遍历算法：
后序遍历是指先访问左子树，然后访问右子树，最后访问根节点。在 Go 语言中，可以使用递归实现后序遍历算法。具体实现如下：
//?定义一个树节点结构体
type?TreeNode?struct?{
Val?int
Left?*TreeNode
Right?*TreeNode
}
//?后序遍历算法
func?PostorderTraversal(root?*TreeNode)?{
if?root?==?nil?{
return
}
//?递归访问左右子树
PostorderTraversal(root.Left)
PostorderTraversal(root.Right)
//?访问当前节点
fmt.Printf("%d?",?root.Val)
}
以上两个算法都是使用递归实现的，时间复杂度为 O(n)，空间复杂度为 O(h)，其中 h 是树的高度。
在这里插入图片描述
在这里插入图片描述灵小智，代码正常运行：
在Go语言中，可以使用递归的方式实现树的先序遍历和后序遍历算法。下面是相应的实现：
package?main
import?"fmt"
//?树的节点结构定义
type?TreeNode?struct?{
Val??????int
Children?[]*TreeNode
}
//?先序遍历函数
func?PreorderTraversal(root?*TreeNode)?{
if?root?==?nil?{
return
}
fmt.Printf("%d?",?root.Val)?//?先输出当前节点的值
for?_,?child?:=?range?root.Children?{
PreorderTraversal(child)?//?递归遍历子节点
}
}
//?后序遍历函数
func?PostorderTraversal(root?*TreeNode)?{
if?root?==?nil?{
return
}
for?_,?child?:=?range?root.Children?{
PostorderTraversal(child)?//?递归遍历子节点
}
fmt.Printf("%d?",?root.Val)?//?最后输出当前节点的值
}
func?main()?{
//?构建一个示例树
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("Preorder?Traversal:")
PreorderTraversal(root)
fmt.Println()
//?后序遍历
fmt.Println("Postorder?Traversal:")
PostorderTraversal(root)
fmt.Println()
}
以上代码通过先序遍历和后序遍历的方式遍历了一棵示例树，并输出了遍历结果。请注意，这里的先序遍历和后序遍历算法的时间复杂度为 O(n)，其中 n 是树中节点的个数。
在这里插入图片描述
在这里插入图片描述chatgpt，代码正常运行：
在Go语言中，可以使用迭代的方式来实现树的先序遍历和后序遍历，以保证时间复杂度为O(n)。以下是示例代码：
package?main
import?(
"fmt"
)
//?树节点结构体
type?Node?struct?{
Value?int
Left??*Node
Right?*Node
}
//?先序遍历
func?PreorderTraversal(root?*Node)?{
if?root?==?nil?{
return
}
stack?:=?[]*Node{root}
for?len(stack)?>?0?{
node?:=?stack[len(stack)-1]
stack?=?stack[:len(stack)-1]
fmt.Printf("%d?",?node.Value)
if?node.Right?!=?nil?{
stack?=?append(stack,?node.Right)
}
if?node.Left?!=?nil?{
stack?=?append(stack,?node.Left)
}
}
}
//?后序遍历
func?PostorderTraversal(root?*Node)?{
if?root?==?nil?{
return
}
stack1?:=?[]*Node{root}
stack2?:=?[]*Node{}
for?len(stack1)?>?0?{
node?:=?stack1[len(stack1)-1]
stack1?=?stack1[:len(stack1)-1]
stack2?=?append(stack2,?node)
//?左子树先入栈
if?node.Left?!=?nil?{
stack1?=?append(stack1,?node.Left)
}
//?右子树后入栈
if?node.Right?!=?nil?{
stack1?=?append(stack1,?node.Right)
}
}
for?i?:=?len(stack2)-1;?i?>=?0;?i--?{
fmt.Printf("%d?",?stack2[i].Value)
}
}
func?main()?{
//?构建一棵树作为示例
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)
}
以上代码中，我们使用了两个栈来实现后序遍历。第一个栈用于模拟先序遍历，将右子节点先入栈，然后左子节点入栈。第二个栈用于保存逆向的结果，在第一个栈为空时，将第一个栈中的元素依次弹出并加入到第二个栈中，然后输出即为后序遍历结果。
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述在这里插入图片描述
- 发表于:
- 原文链接：https://page.om.qq.com/page/OFM-mqKNffwvN5Mw0f1DBWmg0
- 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号（企鹅号）传播渠道之一，根据《腾讯内容开放平台服务协议》转载发布内容。
- 如有侵权，请联系 cloudcommunity@tencent.com 删除。
相关快讯
扫码
添加站长 进交流群
领取专属 10元无门槛券
私享最新 技术干货
腾讯云开发者
