文心一言 VS 讯飞星火 VS chatgpt （124）-- 算法导论10.5 5题

2023-10-30 18:15
文章标签 chatgpt 算法 ai vs 10.5 文心一言 讯飞星火 导论 124

本文主要是介绍文心一言 VS 讯飞星火 VS chatgpt （124）-- 算法导论10.5 5题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

五、用go语言，给定一个n结点的二叉树，写出一个 O(n)时间的非递归过程，将该树每个结点的关键字输出。要求除该树本身的存储空间外只能使用固定量的额外存储空间，且在过程中不得修改该树，即使是暂时的修改也不允许。

文心一言：

您可以使用一个栈来存储节点，以便在遍历二叉树时进行回溯。由于您要求不能修改树的结构，我们需要在原树上进行操作。以下是一个可能的解决方案：

package main  import (  "fmt"  
)  type TreeNode struct {  Val   int  Left  *TreeNode  Right *TreeNode  
}  func PrintTree(root *TreeNode) {  if root == nil {  return  }  stack := []*TreeNode{root}  for len(stack) > 0 {  node := stack[len(stack)-1]  stack = stack[:len(stack)-1]  fmt.Println(node.Val)  if node.Left != nil {  stack = append(stack, node.Left)  }  if node.Right != nil {  stack = append(stack, node.Right)  }  }  
}

在这个函数中，我们首先检查根节点是否为空。如果为空，那么就直接返回。否则，我们将根节点放入栈中。然后，我们开始一个循环，只要栈不为空，就持续运行。在每个循环中，我们取出栈顶的节点，打印其值，然后依次将其左子节点和右子节点（如果存在）放入栈中。这样，我们就可以按照中序遍历的顺序打印出每个节点的值，而中序遍历是二叉树所有遍历方法中最接近线性时间的。同时，因为我们只使用了固定数量的额外存储空间（即栈的空间），所以满足了题目中的要求。

在这里插入图片描述

在这里插入图片描述

讯飞星火：

解析：

1.首先，我们需要创建一个二叉树节点的结构体，包含关键字和左右子节点的指针。

2.然后，我们需要创建一个非递归的过程来遍历二叉树。我们可以使用一个栈来实现这个过程。初始时，我们将根节点压入栈中。

3.在每一步中，我们从栈顶取出一个节点，输出它的关键字，然后将它的右子节点和左子节点（如果存在的话）压入栈中。这样，我们就可以按照先序遍历的顺序访问所有的节点。

4.重复这个过程，直到栈为空，也就是我们已经访问了所有的节点。

代码如下：

package mainimport "fmt"// 定义二叉树节点的结构体
type TreeNode struct {Val   intLeft  *TreeNodeRight *TreeNode
}// 非递归过程遍历二叉树并输出每个节点的关键字
func printTree(root *TreeNode) {if root == nil {return}stack := []*TreeNode{root}for len(stack) > 0 {node := stack[len(stack)-1]stack = stack[:len(stack)-1]fmt.Println(node.Val)if node.Right != nil {stack = append(stack, node.Right)}if node.Left != nil {stack = append(stack, node.Left)}}
}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}printTree(root)
}

这段代码首先定义了一个二叉树节点的结构体，然后定义了一个非递归的过程来遍历二叉树并输出每个节点的关键字。在主函数中，我们创建了一个简单的二叉树进行测试。

在这里插入图片描述

在这里插入图片描述

360智脑：

以下是一个用Go语言实现的非递归遍历二叉树并输出每个结点的关键字的示例代码。这个代码使用了栈来辅助实现，因此时间复杂度为O(n)。

package mainimport ("fmt"
)// 定义二叉树节点
type Node struct {key  intleft； *Noderight *Node
}// 打印二叉树结点
func printTree(root *Node) {if root == nil {return}stack := []*Node{}stack = append(stack, root)for len(stack) > 0 {node := stack[len(stack)-1]stack = stack[:len(stack)-1]fmt.Printf("Node: %d\n", node.key)// 弹出左子节点和右子节点if node.left != nil {stack = append(stack, node.left)}if node.right != nil {stack = append(stack, node.right)}}
}// 定义主函数
func main() {// 创建二叉树root := &Node{key: 100}root.left = &Node{key: 50}root.right = &Node{key: 300}root.left.left = &Node{key: 20}root.left.right = &Node{key: 40}// 打印结点printTree(root)
}

在这个代码中，我们使用了一个栈来存储待处理的二叉树的节点。每次取出一个节点，然后弹出它的左右子节点，并将这些节点存储在一个新的栈中。这样，我们就可以在不修改原始树的情况下，将所有节点的关键字输出。

在这里插入图片描述

在这里插入图片描述

智谱清言：

在 Go 语言中，我们可以使用迭代的方式遍历二叉树，并输出每个节点的关键字。为此，我们可以使用一个长度为 n 的数组作为辅助空间，同时在遍历过程中，按照层序遍历的方式访问每个节点。以下是一个满足要求的 Go 代码实现：

package main
import "fmt"
type TreeNode struct {  Key   int  Left  *TreeNode  Right *TreeNode  
}
func levelOrderTraversal(root *TreeNode, extraSpace int) {  if root == nil {  return  }nodes := make([]*TreeNode, extraSpace)  nodes[0] = root  level := 1for len(nodes) > 0 {  for i := 0; i < len(nodes); i++ {  node := nodes[i]  fmt.Print(node.Key, " ")if node.Left != nil {  nodes = append(nodes, node.Left)  }  if node.Right != nil {  nodes = append(nodes, node.Right)  }  }  fmt.Println()  level++for len(nodes) > 0 && level <= extraSpace {  nodes = nodes[1:]  level++  }  }  
}
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.Right = &TreeNode{Key: 6}levelOrderTraversal(root, 2)  
}

在这个代码中，我们定义了一个TreeNode结构体，用于表示二叉树的节点。levelOrderTraversal函数接受一个二叉树的根节点和一个额外的存储空间大小作为参数。我们使用一个循环遍历二叉树，按照层序访问每个节点，并输出关键字。在每次循环中，我们使用辅助数组存储当前层的节点，并在访问完一层后移除该层节点。

注意，这个解决方案使用了额外的存储空间，但满足了题目要求的不修改二叉树的条件。

在这里插入图片描述

在这里插入图片描述

通义千问：

在 Go 语言中，可以使用广度优先搜索（BFS）来实现这个需求。广度优先搜索是一种图形遍历算法，它从根节点开始，首先访问与根节点相邻的所有节点，然后再依次访问这些节点的邻居。

以下是具体的代码实现：

package mainimport ("fmt"
)type TreeNode struct {Value intLeft  *TreeNodeRight *TreeNode
}func PrintTree(root *TreeNode) {if root == nil {return}queue := make([]*TreeNode, 0)queue = append(queue, root)for len(queue) > 0 {node := queue[0]fmt.Println(node.Value)queue = queue[1:]if node.Left != nil {queue = append(queue, node.Left)}if node.Right != nil {queue = append(queue, node.Right)}}
}func main() {root := &TreeNode{Value: 1}root.Left = &TreeNode{Value: 2}root.Right = &TreeNode{Value: 3}root.Left.Left = &TreeNode{Value: 4}root.Left.Right = &TreeNode{Value: 5}root.Right.Left = &TreeNode{Value: 6}root.Right.Right = &TreeNode{Value: 7}PrintTree(root)
}

在这个代码中，我们使用了一个队列来存储待访问的节点。每次从队列的头部取出一个节点进行访问，并将其左右子节点加入到队列的尾部。这样就可以保证所有节点都会被访问到，并且只需要常数级别的额外空间。

在这里插入图片描述

在这里插入图片描述

天工：

以下是用Go语言实现的O(n)时间复杂度的非递归二叉树遍历过程，满足题目要求：

package mainimport "fmt"type TreeNode struct {Val intLeft *TreeNodeRight *TreeNode
}func printInOrder(root *TreeNode) []int {res := []int{}cur := rootfor cur != nil {if cur.Left == nil {res = append(res, cur.Val)cur = cur.Right} else {printInOrder(cur.Left)res = append(res, cur.Val)cur = cur.Right}}return res
}func main() {root := &TreeNode{1, &TreeNode{2, &TreeNode{4, nil, nil}, &TreeNode{5, nil, nil}}, &TreeNode{3, nil, nil}}fmt.Println(printInOrder(root)) // Output: [1 2 4 5 3]
}

在这个实现中，我们使用了一个辅助函数printInOrder，它使用一个res切片来存储遍历结果，同时维护一个cur指针来指向当前要访问的节点。在每次迭代中，我们首先检查cur的左子节点是否为空，如果为空，说明cur是一个叶节点，我们将cur的值加入到res中，并将cur指向其右子节点。如果cur的左子节点不为空，说明cur有左子节点和右子节点，我们先递归访问其左子节点，直到找到叶节点，然后将cur的值加入到res中，并将cur指向其右子节点。这样，我们就可以按照中序遍历的遍历顺序遍历整个树，并将每个节点的值保存到res切片中，最后返回res切片即可。

在这里插入图片描述

在这里插入图片描述

灵小智：

要实现非递归地遍历二叉树并输出每个节点的关键字，我们可以使用栈来模拟递归的过程。具体地，我们从根节点开始，将其入栈，然后遍历其左子树并将所有经过的节点入栈，直到遇到一个没有左孩子的节点。此时，我们弹出栈顶节点，输出其关键字，并遍历其右子树，将其右孩子以及其右孩子的左子树入栈。我们继续重复该过程，直到栈为空。由于每个节点最多入栈一次，出栈一次，因此时间复杂度为O(n)，且空间复杂度为O(h)，其中h为树的高度。

以下是用Go语言实现该算法的示例代码：

type TreeNode struct {Val intLeft *TreeNodeRight *TreeNode
}func inorderTraversal(root *TreeNode) []int {if root == nil {return []int{}}var result []intvar stack []*TreeNodefor root != nil || len(stack) > 0 {for root != nil {stack = append(stack, root)root = root.Left}root = stack[len(stack)-1]stack = stack[:len(stack)-1]result = append(result, root.Val)root = root.Right}return result
}

该函数实现了二叉树的中序遍历，并返回每个节点的关键字。我们使用一个栈来保存经过的节点，在遍历当前节点的左子树时，将所有经过的节点入栈。当遇到一个没有左孩子的节点时，我们弹出栈顶节点并输出其关键字，并遍历以该节点为根的右子树，将其右孩子以及其右孩子的左子树入栈。重复该过程直到栈为空。

在这里插入图片描述

在这里插入图片描述

chatgpt：

下面是使用Go语言编写的非递归过程，按照中序遍历输出二叉树每个节点的关键字：

package mainimport "fmt"type TreeNode struct {Val   intLeft  *TreeNodeRight *TreeNode
}func inorderTraversal(root *TreeNode) []int {var result []int     // 存储结果的数组stack := []*TreeNode{}   // 使用栈辅助进行迭代current := rootfor current != nil || len(stack) > 0 {// 将左子树的所有节点入栈for current != nil {stack = append(stack, current)current = current.Left}// 弹出栈顶元素并记录值current = stack[len(stack)-1]stack = stack[:len(stack)-1]result = append(result, current.Val)// 处理右子树current = current.Right}return result
}func main() {// 构建示例二叉树：   1   //                   / \  //                  2   3 //                 / \    //                4   5  root := &TreeNode{Val: 1,Left: &TreeNode{Val: 2,Left: &TreeNode{Val: 4},Right: &TreeNode{Val: 5},},Right: &TreeNode{Val: 3},}result := inorderTraversal(root)fmt.Println(result)     // 输出 [4, 2, 5, 1, 3]
}

这里使用了栈来辅助进行迭代，通过模拟递归过程实现中序遍历。时间复杂度为 O(n)，且只使用了固定量的额外存储空间（栈）。

在这里插入图片描述

在这里插入图片描述

这篇关于文心一言 VS 讯飞星火 VS chatgpt （124）-- 算法导论10.5 5题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/309721。

相关文章

openCV中KNN算法的实现

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库，它提供了各
阅读更多...
springboot+dubbo实现时间轮算法

springboot+dubbo实现时间轮算法

《springboot+dubbo实现时间轮算法》时间轮是一种高效利用线程资源进行批量化调度的算法,本文主要介绍了springboot+dubbo实现时间轮算法,文中通过示例代码介绍的非常详细,对大家... 目录前言一、参数说明二、具体实现1、HashedwheelTimer2、createWheel3、n
阅读更多...
SpringBoot实现MD5加盐算法的示例代码

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.
阅读更多...
基于Flask框架添加多个AI模型的API并进行交互

基于Flask框架添加多个AI模型的API并进行交互

《基于Flask框架添加多个AI模型的API并进行交互》：本文主要介绍如何基于Flask框架开发AI模型API管理系统,允许用户添加、删除不同AI模型的API密钥,感兴趣的可以了解下... 目录1. 概述2. 后端代码说明2.1 依赖库导入2.2 应用初始化2.3 API 存储字典2.4 路由函数2.5 应
阅读更多...
Java时间轮调度算法的代码实现

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组（时间轮）和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时
阅读更多...
Spring AI ectorStore的使用流程

Spring AI ectorStore的使用流程

《SpringAIectorStore的使用流程》SpringAI中的VectorStore是一种用于存储和检索高维向量数据的数据库或存储解决方案,它在AI应用中发挥着至关重要的作用,本文给大家介... 目录一、VectorStore的基本概念二、VectorStore的核心接口三、VectorStore的
阅读更多...
如何通过Golang的container/list实现LRU缓存算法

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣：146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.
阅读更多...
Spring AI集成DeepSeek三步搞定Java智能应用的详细过程

Spring AI集成DeepSeek三步搞定Java智能应用的详细过程

《SpringAI集成DeepSeek三步搞定Java智能应用的详细过程》本文介绍了如何使用SpringAI集成DeepSeek,一个国内顶尖的多模态大模型,SpringAI提供了一套统一的接口,简... 目录DeepSeek 介绍Spring AI 是什么？Spring AI 的主要功能包括1、环境准备2
阅读更多...
Spring AI集成DeepSeek实现流式输出的操作方法

Spring AI集成DeepSeek实现流式输出的操作方法

《SpringAI集成DeepSeek实现流式输出的操作方法》本文介绍了如何在SpringBoot中使用Sse（Server-SentEvents）技术实现流式输出,后端使用SpringMVC中的S... 目录一、后端代码二、前端代码三、运行项目小天有话说题外话参考资料前面一篇文章我们实现了《Spring
阅读更多...
Spring AI与DeepSeek实战一之快速打造智能对话应用

Spring AI与DeepSeek实战一之快速打造智能对话应用

《SpringAI与DeepSeek实战一之快速打造智能对话应用》本文详细介绍了如何通过SpringAI框架集成DeepSeek大模型,实现普通对话和流式对话功能,步骤包括申请API-KEY、项目搭... 目录一、概述二、申请DeepSeek的API-KEY三、项目搭建3.1. 开发环境要求3.2. mav
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2