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

福大大架构师每日一题

发布于 2023-10-27 15:13:08

1880

发布于 2023-10-27 15:13:08

文章被收录于专栏：福大大架构师每日一题

二、用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 main
import "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 是二叉树节点的数量。