写点什么

文心一言 VS 讯飞星火 VS chatgpt (121)-- 算法导论 10.4 2 题

  • 2023-10-26
    北京
  • 本文字数:3143 字

    阅读完需:约 10 分钟

二、用 go 语言,给定一个 n 结点的二叉树,写出一个 O(n)时间的递归过程,将该树每个结点的关键字输出。

文心一言:

在 Go 语言中,你可以使用递归函数来遍历二叉树的所有节点,并输出每个节点的关键字。以下是一个示例代码:


package main    import "fmt"    // TreeNode 结构定义  type TreeNode struct {   Key     int   Left    *TreeNode   Right   *TreeNode  }    // PrintTree 递归遍历二叉树并输出每个节点的关键字  func PrintTree(root *TreeNode) {   if root == nil {   return   }     fmt.Println(root.Key)   PrintTree(root.Left)   PrintTree(root.Right)  }    func main() {   // 构造一个二叉树   root := &TreeNode{Key: 1}   root.Left = &TreeNode{Key: 2}   root.Right = &TreeNode{Key: 3}   root.Left.Left = &TreeNode{Key: 4}   root.Left.Right = &TreeNode{Key: 5}     // 遍历并输出每个节点的关键字   PrintTree(root)  }
复制代码


在这个示例中,PrintTree 函数是一个递归函数,它首先输出当前节点的关键字,然后递归地遍历左子树和右子树。这个过程的时间复杂度是 O(n),其中 n 是二叉树中的节点数。



讯飞星火:

首先,我们需要定义一个二叉树节点的结构体,然后编写一个递归函数来遍历二叉树并输出每个节点的关键字。


解析:


  1. 定义一个二叉树节点结构体 TreeNode,包含关键字 key 和左右子节点 left 和 right。

  2. 编写一个递归函数 traverse,接收一个二叉树节点作为参数。

  3. 如果当前节点为空,直接返回。

  4. 输出当前节点的关键字。

  5. 递归调用 traverse 函数,传入左子节点和右子节点。


代码如下:


package main
import "fmt"
type TreeNode struct { key int left *TreeNode right *TreeNode}
func traverse(node *TreeNode) { if node == nil { return } fmt.Println(node.key) traverse(node.left) traverse(node.right)}
func main() { // 创建一个示例二叉树 root := &TreeNode{key: 1} root.left = &TreeNode{key: 2} root.right = &TreeNode{key: 3} root.left.left = &TreeNode{key: 4} root.left.right = &TreeNode{key: 5} root.right.left = &TreeNode{key: 6} root.right.right = &TreeNode{key: 7}
// 遍历二叉树并输出每个节点的关键字 traverse(root)}
复制代码


这段代码首先定义了一个二叉树节点结构体 TreeNode,然后编写了一个递归函数 traverse 来遍历二叉树并输出每个节点的关键字。在 main 函数中,我们创建了一个示例二叉树,并调用 traverse 函数遍历并输出每个节点的关键字。



360 智脑:

以下是一个使用 Go 语言实现的简单二叉树遍历的递归函数,可以输出二叉树中每个结点的关键字:


package main
import ( "fmt")
// 定义二叉树节点结构体type Node struct { Key int Left *Node Right *Node}
// 递归二叉树遍历函数func printTree(node *Node) { if node == nil { return } fmt.Println(node.Key) printTree(node.Left) printTree(node.Right)}
func main() { // 初始化根节点 root := &Node{Key: 10} // 遍历整个二叉树 printTree(root)}
复制代码


该程序首先定义了一个Node结构体来表示二叉树中的节点,其中包含了结点的关键字和左右子树的指针。然后,定义了一个printTree()递归函数来遍历二叉树,该函数首先检查当前节点是否为nil,如果是则返回,否则输出当前节点的关键字,并递归地遍历左右子树。最后,在main()函数中,初始化了一个包含 10 个节点的二叉树,并调用了printTree()函数遍历整个二叉树,输出每个节点的关键字。



智谱清言:

package mainimport "fmt"type TreeNode struct {      Key   int      Left  *TreeNode      Right *TreeNode  }func preOrderTraversal(root *TreeNode) {      if root == nil {          return      }    fmt.Print(root.Key, " ")      preOrderTraversal(root.Left)      preOrderTraversal(root.Right)  }func main() {      root := &TreeNode{Key: 1}      root.Left = &TreeNode{Key: 2}      root.Right = &TreeNode{Key: 3}      root.Left.Left = &TreeNode{Key: 4}      root.Left.Right = &TreeNode{Key: 5}      root.Right.Left = &TreeNode{Key: 6}      root.Right.Right = &TreeNode{Key: 7}    preOrderTraversal(root)  }
复制代码


这个代码定义了一个二叉树的结构体,并实现了 preOrderTraversal 函数,该函数接受一个树根作为参数,并按照先序遍历的顺序输出每个结点的关键字。先序遍历的顺序是:根 -> 左子树 -> 右子树。递归过程中,时间复杂度为 O(n),其中 n 为树中结点的数量。


通义千问:

在 Go 语言中,我们可以使用递归来遍历二叉树并打印出每个节点的值。以下是一个简单的实现:


type TreeNode struct {    Val   int    Left  *TreeNode    Right *TreeNode}
func printTree(root *TreeNode) { if root != nil { fmt.Println(root.Val) printTree(root.Left) printTree(root.Right) }}
复制代码


在这个代码中,printTree函数接收一个指向二叉树根节点的指针作为参数。如果这个节点不为空(即root != nil),则首先打印出该节点的值,然后递归地调用printTree函数来遍历左子树和右子树。


这个算法的时间复杂度是 O(n),因为我们需要访问二叉树中的每一个节点一次。无论二叉树是平衡的还是不平衡的,我们都需要进行同样的操作。


注意:这个实现假设二叉树的值已经存储在Val字段中。如果你需要从其他字段获取值,你只需要修改fmt.Println(root.Val)这一行即可。


天工:

以下是用 Go 语言实现的 O(n)时间递归过程,将二叉树中每个结点的关键字输出:


type TreeNode struct {    Val int    Left *TreeNode    Right *TreeNode}
func printTree(root *TreeNode) { printTreeHelper(root, 0)}
func printTreeHelper(node *TreeNode, level int) { if node == nil { return } for i := 0; i < level; i++ { fmt.Print("\t") } fmt.Printf("%d\n", node.Val) printTreeHelper(node.Left, level+1) printTreeHelper(node.Right, level+1)}
复制代码


这里定义了一个TreeNode结构体表示二叉树的结点,包括该结点的值、左子树和右子树。printTree函数是主函数,它调用了printTreeHelper辅助函数来递归地遍历整个二叉树,并输出每个结点的值。在printTreeHelper函数中,我们首先检查当前结点是否为空,如果为空则直接返回。否则,我们使用一个循环来输出当前结点的值,并递归地遍历其左子树和右子树。由于每个结点的深度最多为 O(log n),因此整个递归过程的时间复杂度为 O(n)。


chatgpt:

以下是使用 Go 语言编写的递归过程,以将二叉树每个节点的关键字输出:


package main
import "fmt"
type TreeNode struct { Val int Left *TreeNode Right *TreeNode}
func inorderTraversal(root *TreeNode) { if root == nil { return }
inorderTraversal(root.Left) fmt.Println(root.Val) inorderTraversal(root.Right)}
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}
// 输出二叉树节点的关键字 inorderTraversal(root)}
复制代码


在这个例子中,inorderTraversal 函数通过中序遍历方式递归地访问左子树、当前节点和右子树,从而将每个节点的关键字打印出来。整个过程时间复杂度为 O(n),其中 n 是二叉树节点的数量。



发布于: 刚刚阅读数: 5
用户头像

公众号:福大大架构师每日一题 2021-02-15 加入

公众号:福大大架构师每日一题

评论

发布
暂无评论
文心一言 VS 讯飞星火 VS chatgpt (121)-- 算法导论10.4 2题_福大大架构师每日一题_福大大架构师每日一题_InfoQ写作社区