首页 > 编程语言 >文心一言 VS 讯飞星火 VS chatgpt （143）-- 算法导论12.1 3题

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

时间：2023-11-26 21:02:41浏览次数：45  
标签：Right TreeNode 143 nil VS 文心 root stack Left

三、用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 算法，它不需要额外的栈空间，但需要对指针进行特殊处理。在此不再赘述。

在这里插入图片描述

在这里插入图片描述

标签：Right,TreeNode,143,nil,VS,文心,root,stack,Left
From： https://www.cnblogs.com/moonfdd/p/17857937.html

相关文章

  • 【渗透测试】工具实践之AWVS
    AWVS安装及使⽤使⽤docker安装dockerpullxrsec/awvs启动镜像https://hub.docker.com/r/xrsec/awvs参考链接下载破解脚本，在本地执⾏登录⽤户名密码发起扫描转到“添加⽬标”⻚⾯以配置要扫描的新⽹站：dockerrun-it-d\--nameawvs\-p3443:3443\xrsec/awvs:latestwgethttps......
  • 惊喜小现：园子的 VSCode 插件
    园子的vscode插件自从2021年12月29日在vscodemarketplace上发布第一版本v0.05以来，已经快两年了。那时我们刚刚忙完忙了大半年的网站整改，百废不知从何处开始兴，一位.NET全栈开发同事一时兴趣边学边做，尝试开发园子的vscode插件。一开始就采用开源的方式，代码托管在git......
  • 【Python】使用vscode编码提示找不到模块
    问题描述已经使用pip安装了模块，但是使用vscode没有代码提示。解决办法这种情况一般是因为pc安装了多个python版本，安装模块的pip不是vscode指定的编译环境。点击右下角，选择环境变量中配置的python版本。解决问题：......
  • CSharp: vs 2022
    package.json {"name":"healthcheck","version":"0.0.0","scripts":{"ng":"ng","start":"echoStarting...&&ngserve","build&......
  • 新手VSCode配置C++20
    最近买了本C++20的书，想要自己配置下在VScode的环境例子代码：#include<iostream>#include<format>intmain(){std::cout<<std::format("Hello,world!{0}",123)<<std::endl;//输出：Hello,world!123std::stringstr=std::format("......
  • P1439 【模板】最长公共子序列
    前置知识：\(LIS\):即最长上升子序列(\(Longest\)\(Increasing\)\(Subsequence\))LuoguB3637最长上升子序列这是一个简单的动规板子题。给出一个由\(n(n\le5000)\)个不超过\(10^6\)的正整数(\(x_1,x_2,\cdots,x_n\))组成的序列。请输出这个序列的最长上升子......
  • 工具 | Vshell使用入门
    写在前面   "Vshell是一款go编写的主机群管理工具（RAT）"。    发现Vshell作者团队非常低调，项目Github上Readme介绍非常简短，网上也很少有使用介绍。写个基础入门，记录从配置到主机管理、搭建隧道。本文仅作为工具介绍，请勿用于任何违法场景。    未经授权请勿利用文章......
  • windows中vscode通过ssh连接linux 保存公钥 运行c程序
    1、首先，vscode下载以下几个扩展，c/c++、remotedevelopment 2、下载完成后编写自己的linux连接配置文件 配置文件包括host、hostname、user和port，以下是我的配置，编辑完成保存，然后直接新建连接即可 3、新建的连接每次重连都需要输入密码，通过ssh公钥来解决首先，打开windo......
  • JVS低代码表单组件：单选与多选组件全解析
    在现代化的数字界面中，组件是不可或缺的一部分。无论是在问卷调查、投票，还是在购物车等场景中，单选和多选组件都扮演着重要角色。它们让用户能够在一系列选项中做出决定，从而提高交互的效率和用户体验。JVS低代码表单组件中提供了单选与多选的组件，接下来我们结合场景详细介绍单选与多......
  • UEC++中VS标红误报解决办法
    实测可行：1、打开工程2、右键工程->属性3、左侧找到NMake4、然后在打开的右侧界面中找到"包含搜索路径(IncludeSearchPath)"，点击并选择编辑5、添加新路径$(SolutionDir)Intermediate\Build\Win64\UE4Editor\Inc\$(SolutionName)6、插件的路径需要修改具体的插件路径7、将......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99