文心一言 VS 讯飞星火 VS chatgpt （143）-- 算法导论12.1 3题

三、用go语言，设计一个执行中序遍历的非递归算法。（提示:一种容易的方法是使用栈作为辅助数据结构;另一种较复杂但比较简洁的做法是不使用栈，但要假设能测试两个指针是否相等。）

文心一言，代码正常运行：

我们可以使用栈作为辅助数据结构来执行中序遍历的非递归算法。以下是用Go语言实现的代码：

package main  
  
import (  
 "fmt"  
)  
  
type TreeNode struct {  
 Val   int  
 Left  *TreeNode  
 Right *TreeNode  
}  
  
func inorderTraversal(root *TreeNode) {  
 stack := []*TreeNode{}  
 node := root  
  
 for node != nil || len(stack) > 0 {  
 for node != nil {  
 stack = append(stack, node)  
 node = node.Left  
 }  
  
 node = stack[len(stack)-1]  
 stack = stack[:len(stack)-1]  
 fmt.Println(node.Val)  
  
 node = node.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)  
}

这个程序定义了一个TreeNode结构体，每个节点有一个整数值和两个指向其左右子节点的指针。inorderTraversal函数接收一个树的根节点，并使用栈来进行中序遍历。在遍历过程中，首先将当前节点及其所有左子节点推入栈中，然后处理栈顶节点（即最深层的左子节点），打印其值并将节点从栈中弹出。然后转向处理该节点的右子节点。如果在任何时候栈为空且当前节点为nil，则遍历结束。

在这里插入图片描述

在这里插入图片描述

讯飞星火，代码正常运行：

package main

import "fmt"

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func inorderTraversal(root *TreeNode) []int {
    stack := []*TreeNode{}
    curr := root
    var res []int

    for curr != nil || len(stack) > 0 {
        for curr != nil {
            stack = append(stack, curr)
            curr = curr.Left
        }
        curr = stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        res = append(res, curr.Val)
        curr = curr.Right
    }

    return res
}

func main() {
    root := &TreeNode{Val: 1}
    root.Right = &TreeNode{Val: 2}
    root.Right.Left = &TreeNode{Val: 3}

    fmt.Println(inorderTraversal(root)) // Output: [1 3 2]
}

在这里插入图片描述

在这里插入图片描述

360智脑，代码不能运行：

使用栈实现中序遍历的非递归算法：

package main

import (
    "fmt"
)

// BinaryTree is a simple implementation of binary tree node.
type BinaryTree struct {
    Data interface{}
    Left *BinaryTree
    Right *BinaryTree
}

// InOrderNoRecursion is an implementation of in-order traversal without recursion.
func (bt *BinaryTree) InOrderNoRecursion() []interface{} {
    res := []interface{}{}
    stack := []interface{}{bt}

    for len(stack) > 0 {
        for bt != nil {
            stack = stack[1:]
            stack = stack[0:1]
            bt = bt.Left
        }
        if len(stack) == 0 {
            break
        }
        var current interface{}
        for _, element := range stack {
            current = element
        }
        res = append(res, current.(interface{})) // visit current node
        stack = stack[1:]
        bt = bt.Right
    }
    return res
}

func init() {
    // Create an empty binary tree.
    root := &BinaryTree{}
    root.Left = &BinaryTree{}
    root.Right = &BinaryTree{}
    
    // Create an empty binary tree for testing.
    testRoot := &BinaryTree{}
    testRoot.Left = &BinaryTree{}
    testRoot.Right = &BinaryTree{}
    
    fmt.Println("In-order traversal without recursion result:", InOrderNoRecursion(root))
    fmt.Println("In-order traversal without recursion result:", InOrderNoRecursion(testRoot))
}

该代码首先创建了一个空二叉树，然后创建两个测试用的二叉树进行测试。在InOrderNoRecursion()方法中，我们使用了栈来模拟中序遍历的过程。每次遍历到一个节点时，将其加入栈中，然后移动到其左子树或右子树。当栈为空时，表示已经遍历完所有节点，此时返回结果数组即可。

在这里插入图片描述

在这里插入图片描述

智谱清言，第1段代码正常运行，第2段代码抛panic：

以下是使用栈作为辅助数据结构的非递归算法实现：

package main
import "fmt"
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}
func inorderTraversal(root *TreeNode) []int {
    if root == nil {
        return []int{}
    }
    result := make([]int, 0)
    stack := make([]*TreeNode, 0)
    current := root
    for 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() {
    root := &TreeNode{Val: 1, Left: &TreeNode{Val: 2, Left: &TreeNode{Val: 3, Left: nil, Right: nil}, Right: nil}, Right: &TreeNode{Val: 4, Left: nil, Right: nil}}
    fmt.Println(inorderTraversal(root)) // 输出：[3 2 4 1]
}

以下是使用非递归但假设能测试两个指针是否相等的做法：

package main
import "fmt"
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}
func isEqual(a, b *TreeNode) bool {
    if a == nil && b == nil {
        return true
    }
    if a == nil || b == nil {
        return false
    }
    return a.Val == b.Val && isEqual(a.Left, b.Left) && isEqual(a.Right, b.Right)
}
func inorderTraversal(root *TreeNode) []int {
    if root == nil {
        return []int{}
    }
    result := make([]int, 0)
    current := root
    for current != nil {
        for isEqual(current.Left, current) {
            current = current.Left
        }
        result = append(result, current.Val)
        for !isEqual(current.Right, current) {
            current = current.Right
        }
        current = current.Right
    }
    return result
}
func main() {
    root := &TreeNode{Val: 1, Left: &TreeNode{Val: 2, Left: &TreeNode{Val: 3, Left: nil, Right: nil}, Right: nil}, Right: &TreeNode{Val: 4, Left: nil, Right: nil}}
    fmt.Println(inorderTraversal(root)) // 输出：[3 2 4 1]
}

这两种方法都可以实现中序遍历，但第二种方法不使用栈，而是假设能测试两个指针是否相等，这种假设在实际编程中可能不总是成立，因此第一种方法更为推荐。

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

通义千问，两段代码都能正常运行：

以下是两种方法实现的Go语言代码：

方法一：使用栈作为辅助数据结构

package main

import (
	"fmt"
)

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func inorderTraversal(root *TreeNode) []int {
	var res []int
	if root == nil {
		return res
	}
	stack := []*TreeNode{}
	for node := root; node != nil || len(stack) > 0; {
		for node != nil {
			stack = append(stack, node)
			node = node.Left
		}
		node = stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		res = append(res, node.Val)
		node = node.Right
	}
	return res
}

func main() {
	root := &TreeNode{Val: 1}
	root.Left = &TreeNode{Val: 2}
	root.Right = &TreeNode{Val: 3}
	fmt.Println(inorderTraversal(root)) // 输出: [2 1 3]
}

方法二：不使用栈，测试两个指针是否相等

package main

import (
	"fmt"
)

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func inorderTraversal(root *TreeNode) []int {
	var res []int
	if root == nil {
		return res
	}
	cur := root
	for cur != nil {
		if cur.Left != nil {
			tmp := cur.Left
			for tmp.Right != nil && tmp.Right != cur {
				tmp = tmp.Right
			}
			if tmp.Right == nil {
				tmp.Right = cur
				cur = cur.Left
				continue
			} else {
				tmp.Right = nil
			}
		}
		res = append(res, cur.Val)
		cur = cur.Right
	}
	return res
}

func main() {
	root := &TreeNode{Val: 1}
	root.Left = &TreeNode{Val: 2}
	root.Right = &TreeNode{Val: 3}
	fmt.Println(inorderTraversal(root)) // 输出: [2 1 3]
}

这两种方法都可以有效地对二叉树进行中序遍历，并且都不会修改原始的二叉树结构。

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

天工，代码正常运行：

以下是使用栈实现中序遍历的非递归算法的Go代码示例：

package main

import "fmt"

type TreeNode struct {
    Val int
    Left *TreeNode
    Right *TreeNode
}

func inorderTraversal(root *TreeNode) []int {
    res := []int{}
    stack := []*TreeNode{root}
    for len(stack) > 0 {
        node := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        if node.Left != nil {
            stack = append(stack, node.Left)
        }
        if node.Right != nil {
            stack = append(stack, node.Right)
        }
        res = append(res, node.Val)
    }
    return res
}

func main() {
    root := &TreeNode{1, &TreeNode{2, nil, nil}, &TreeNode{3, nil, nil}}
    res := inorderTraversal(root)
    fmt.Println(res) // Output: [2 1 3]
}

该代码定义了一个TreeNode结构体，表示二叉树的节点，包含节点的值Val，左子树Left和右子树Right。inorderTraversal函数使用一个栈来模拟中序遍历的过程，将根节点入栈，然后循环处理直到栈为空。在每次循环中，将栈顶节点弹出，如果该节点有左子树，则将左子树入栈，如果该节点有右子树，则将右子树入栈，最后将该节点的值加入到结果数组中。最后返回结果数组。

在main函数中，创建了一个二叉树的根节点，并调用inorderTraversal函数对其进行中序遍历，并将结果打印到控制台上。输出结果为[2 1 3]，与预期结果一致。

在这里插入图片描述

在这里插入图片描述

灵小智：

以下是使用栈作为辅助数据结构的非递归算法，用于执行中序遍历：

// 树节点定义
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

// 中序遍历函数
func inorderTraversal(root *TreeNode) []int {
    if root == nil {
        return nil
    }

    stack := []*TreeNode{}
    result := []int{}
    currentNode := root

    for currentNode != nil || len(stack) >  {
        // 将当前节点及其所有左子节点入栈
        for currentNode != nil {
            stack = append(stack, currentNode)
            currentNode = currentNode.Left
        }

        // 弹出栈顶节点并记录其值
        currentNode = stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        result = append(result, currentNode.Val)

        // 处理右子节点
        currentNode = currentNode.Right
    }

    return result
}

这个算法使用了一个栈来存储待处理的节点。首先将根节点及其所有左子节点依次入栈，然后弹出栈顶节点并记录其值，最后处理右子节点。重复这个过程直到栈为空且当前节点为空。

使用这个算法可以实现中序遍历的非递归方式。希望这个代码对你有帮助！

在这里插入图片描述

在这里插入图片描述

chatgpt：

下面是使用栈作为辅助数据结构的非递归中序遍历算法的示例代码：

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func inorderTraversal(root *TreeNode) []int {
    if root == nil {
        return nil
    }

    stack := []*TreeNode{}
    res := []int{}
    curr := root

    for curr != nil || len(stack) > 0 {
        // 将当前节点及其左子树入栈，直到没有左子节点为止
        for curr != nil {
            stack = append(stack, curr)
            curr = curr.Left
        }
        
        // 弹出栈顶元素，并将其值添加到结果数组中
        top := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        res = append(res, top.Val)

        // 处理右子树
        curr = top.Right
    }

    return res
}

这个算法使用了一个辅助栈，通过模拟递归过程来实现非递归的中序遍历。具体步骤如下：

1.如果当前节点不为空或者栈不为空，则继续循环。

2.将当前节点以及它的所有左子节点依次入栈，直到当前节点为空。

3.弹出栈顶元素，将其值添加到结果数组中。

4.处理弹出节点的右子节点。

以上是一种常见且简单易懂的方法。另外一种复杂但更简洁的方法是使用 Morris Traversal 算法，它不需要额外的栈空间，但需要对指针进行特殊处理。在此不再赘述。

在这里插入图片描述

在这里插入图片描述

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/190578.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

基于51单片机的智能垃圾桶硬件设计

基于51单片机的智能垃圾桶硬件设计

**单片机设计介绍， 基于51单片机的智能垃圾桶硬件设计 文章目录 一 概要二、功能设计设计思路 三、 软件设计原理图 五、 程序六、 文章目录 一 概要 基于51单片机的智能垃圾桶设计旨在通过传感器和控制电路实现智能化的垃圾桶功能。下面是一个简要的硬件设计介绍&…
阅读更多...
HCIA-RS基础-距离矢量路由协议

HCIA-RS基础-距离矢量路由协议

前言： 动态路由协议根据寻径方式可以分为距离矢量路由协议和链路状态路由协议。本文将详细介绍距离矢量路由协议的原理，并阐述其中一个重要概念——路由环路，同时介绍如何避免路由环路的方法。通过学习本文，您将能够深入理解距离矢…
阅读更多...
什么是CAS/CAS的应用/CAS的ABA问题

什么是CAS/CAS的应用/CAS的ABA问题

文章目录 CAS1. 什么是CAS2. CAS的应用2.1 实现原子类2.2 实现自旋锁 3. CAS的ABA问题3.1 什么是ABA问题3.2 ABA问题引来的BUG3.3 解决方案 CAS 1. 什么是CAS CAS: 全称Compare and swap, 字面意思:”比较并交换“. 操作: 设V为内存中的值, A为寄存器中的值(旧的预期值), B也…
阅读更多...
火柴棒等式

火柴棒等式

枚举 只要在保证等式正确的基础上判断火柴棒有没有用完就可以 因为数比较小，而且我不知道最大的等式中的数是多少，索性就设置为999了 还好对效率要求不大（doge） 要不然就得自己慢慢改最大数来试了 代码如下： #in…
阅读更多...
Android 单元测试初体验

Android 单元测试初体验

Android 单元测试初体验 前言一、单元测试是什么？二、简单使用1.依赖2.单元测试代码简单模版及解释 总结 前言 当初在学校学安卓的时候，老师敢教学进度，翻到单元测试这一章节的时候提了两句，没有把单元测试当重点讲，只…
阅读更多...
jQuery_09 事件的绑定与使用(on)

jQuery_09 事件的绑定与使用(on)

jQuery使用on绑定事件 jQuery可以给dom对象添加事件 在程序执行期间动态的处理事件 1. $("选择器").事件名称(事件处理函数) $("选择器") ： 选择0或者多个dom对象 给他们添加事件 事件名称：就是js中事件名称去掉on的部分 比如单击…
阅读更多...
PTA-7-53 身份证排序

PTA-7-53 身份证排序

题目： 输入n，然后连续输入n个身份证号。 将每个身份证的年月日抽取出来，按年-月-日格式组装，然后对组装后的年-月-日升序输出。 根据题目要求，代码实现如下： import java.util.Scanner; import java.uti…
阅读更多...
linux之间的免密通信原来是这么的简单

linux之间的免密通信原来是这么的简单

linux之间的免密通信原来是这么的简单 何为免密通信，说的大白话就是，我连接你的服务器不需要密码，哈哈，就是所谓的免密通信 今天小编也不讲免密的基本原理了哈，原理的话，百度里面有好多 小编的主要目的呢是…
阅读更多...
1.1 半加器

1.1 半加器

输入1输入2结果进位0000101001101101 半加器: 实现1位的加法 根据结果可知输入1与输入2相加结果 -> 符合 异或门进位 -> 符合 与门最终要么有结果要么有进位,不存在即有结果也有进位 异或门的实现也可以由基本的3个 “与或非” 门实现 与:& , 或:| , 非:! 用这3个…
阅读更多...
开通橱窗还能开抖店吗？怎么开通？一篇详解！

开通橱窗还能开抖店吗？怎么开通？一篇详解！

我是电商珠珠 开通商品橱窗之后还能开抖店吗？商品橱窗和抖音小店可以同时开吗？ 一部分人最初的时候，都觉得直播带货很火，所以就自己去买粉丝或是发视频积攒粉丝，等粉丝够了发现，好像和当初想的不太一样&a…
阅读更多...
2017年五一杯数学建模A题公交车排班问题解题全过程文档及程序

2017年五一杯数学建模A题公交车排班问题解题全过程文档及程序

2017年五一杯数学建模 A题 公交车排班问题 原题再现 随着徐州市经济的快速发展，公交车系统对于人们的出行扮演着越来越重要的角色。在公交车资源有限的情况下，合理的编排公交车的行车计划成为公交公司亟待解决的问题。以下给出公交车排班问题中的部分名…
阅读更多...
Java实现-数据结构 2.时间和空间复杂度

Java实现-数据结构 2.时间和空间复杂度

.如何衡量一个算法的好坏：时间复杂度和空间复杂度 算法效率分为时间效率和空间效率，时间效率称为时间复杂度，空间效率称为空间复杂度 时间复杂度 算法的时间复杂度是一个数学函数，它描述了算法的运行时间，一个算法执…
阅读更多...
什么是客户自助服务？综合指南献上~

什么是客户自助服务？综合指南献上~

《哈佛商业评论》曾报道过，81%的消费者在找客服之前会自己先去找办法解决。 如今，客户希望得到更快的响应。他们不想排队去等信息。他们想要的只是一个更快、更可靠的自助服务解决方案。作为企业，应该注意到他们的期望。企业需要做的就是通过…
阅读更多...
2017年五一杯数学建模C题宜居城市问题值解题全过程文档及程序

2017年五一杯数学建模C题宜居城市问题值解题全过程文档及程序

2017年五一杯数学建模 C题 宜居城市问题 原题再现 城市宜居性是当前城市科学研究领域的热点议题之一，也是政府和城市居民密切关注的焦点。建设宜居城市已成为现阶段我国城市发展的重要目标,对提升城市居民生活质量、完善城市功能和提高城市运行效率具有重要意义。…
阅读更多...
2009年iMac装64位windows7及win10

2009年iMac装64位windows7及win10

2009年iMac装64位windows7及win10 Boot Camp没有“创建 Windows7 或更高版本的安装磁盘”选项 安装完Mac OS系统后，要制作Windows7安装U盘时才发现，Boot Camp没有“创建 Windows7 或更高版本的安装磁盘”选项，搜索到文章：修改Boo…
阅读更多...
C语言——深入理解指针（2）

C语言——深入理解指针（2）

目录 1. 数组名 2. 指针访问数组 3. 一维数组的传参（本质） 4. 冒泡排序 5. 二级指针 6. 指针数组（指针的数组） 7. 指针数组模拟二维数组 1. 数组名 在之前的代码中我们使用指针访问过数组的内容。 int arr[10] {1,2,3,4…
阅读更多...
xxljob学习笔记01（小滴课堂）

xxljob学习笔记01（小滴课堂）

分布式调度xxl-job源码部署和数据库建立： 在idea中打开安装包： 创建数据库： 建表： 在项目里： 在navicat里运行语句即可： 修改数据库地址和用户名，密码： 配置令牌，不然谁…
阅读更多...
Linux环境下自动化创建大量的账号

Linux环境下自动化创建大量的账号

参考《鸟哥的Linux私房菜基础篇第四版》13.7.2节微调而成： 下面脚本的目的是为服务器的管理员自动化创建大量的账号，节省生命。 #!/bin/bash # This shell script will create amount of Linux login accounts for you. # 1. check the "accounta…
阅读更多...
探索计算机视觉：深度学习与图像识别的融合

探索计算机视觉：深度学习与图像识别的融合

探索计算机视觉：深度学习与图像识别的融合 摘 要： 本文将探讨计算机视觉领域中的深度学习技术，并重点关注图像识别方面的应用。我们将介绍卷积神经网络（CNN）的原理、常用的图像数据集以及图像识别的实际应用场景&…
阅读更多...
python环境搭建-yolo代码跑通-呕心沥血制作（告别报错no module named torch）

python环境搭建-yolo代码跑通-呕心沥血制作（告别报错no module named torch）

安装软件 安装过的可以查看有没有添加环境变量 好的！ 我们发车！ 如果你想方便快捷的跑通大型项目，那么必须安装以下两个软件: 1.pycharm2.anaconda对应作用： pycharm:专门用来跑通python项目的软件，相当于一个编辑器，可以debug调试，可以接受远程链接调试！anaconda：专…
阅读更多...
最新文章

Copyright @ 2022~2023