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

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

时间：2023-11-27 14:57:37浏览次数：54  
标签：node 144 遍历 TreeNode nil VS 文心 root stack

四、用go语言，对于一棵有 n 个结点的树，请设计在 O(n)时间内完成的先序遍历算法和后序遍历算法。

我个人喜欢 灵小智 。

文心一言：

在 Go 语言中，我们可以使用递归来实现树的前序遍历和后序遍历。以下是实现这两种方法的代码。

首先，我们定义一个树节点的结构：

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

接下来，我们实现前序遍历（根-左-右）：

func preOrderTraversal(root *TreeNode) {  
    if root == nil { // 空节点则返回  
        return  
    }  
    fmt.Println(root.Val) // 先打印根节点  
    preOrderTraversal(root.Left) // 然后遍历左子树  
    preOrderTraversal(root.Right) // 最后遍历右子树  
}

然后，我们实现后序遍历（左-右-根）：

func postOrderTraversal(root *TreeNode) {  
    if root == nil { // 空节点则返回  
        return  
    }  
    postOrderTraversal(root.Left) // 先遍历左子树  
    postOrderTraversal(root.Right) // 然后遍历右子树  
    fmt.Println(root.Val) // 最后打印根节点  
}

以上的前序遍历和后序遍历的时间复杂度都是 O(n)，其中 n 是树的节点数量。这是因为每个节点都会被访问一次，每个节点只会被访问一次。

在这里插入图片描述

在这里插入图片描述

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

package main

import "fmt"

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

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

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

    for len(stack) > 0 {
        node := stack[len(stack)-1]
        stack = stack[:len(stack)-1]

        if node.Right != nil {
            stack = append(stack, node.Right)
            res = append(res, node.Right.Val)
        }

        if node.Left != nil {
            stack = append(stack, node.Left)
            res = append(res, node.Left.Val)
        }
    }

    return res
}

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

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

    for len(stack) > 0 {
        node := stack[len(stack)-1]
        stack = stack[:len(stack)-1]

        res = append(res, node.Val)

        if node.Left != nil {
            stack = append(stack, node.Left)
        }

        if node.Right != nil {
            stack = append(stack, node.Right)
        }
    }

    for i, n := 0, len(res); i < n/2; i++ {
        res[i], res[n-1-i] = res[n-1-i], res[i]
    }

    return res
}

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}
    root.Right.Left = &TreeNode{Val: 6}
    root.Right.Right = &TreeNode{Val: 7}

    fmt.Println("先序遍历结果：", preorderTraversal(root))
    fmt.Println("后序遍历结果：", postorderTraversal(root))
}

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

360智脑，代码不能运行：

以下是用go语言实现一棵有 n 个结点的树的先序遍历和后序遍历算法：

先序遍历算法：

package main
import "fmt"

func preOrder(node *Node) []int {
    res := []int{}
    if node != nil {
        res = append(res, node.val)
        preOrder(node.left)
        preOrder(node.right)
    }
    return res
}

func main() {
    // 创建一棵有3个结点的二叉树
    root := &Node{val: 10, left: nil, right: nil}
    root.left = &Node{val: 5, left: nil, right: &Node{}}
    root.left.left = &Node{val: 3, left: nil, right: nil}
    root.left.right = &Node{val: 7, left: nil, right: nil}
    root.right = &Node{val: 15, left: nil, right: &Node{}}
    root.right.left = &Node{val: 2, left: nil, right: nil}
    root.right.right = &Node{val: 12, left: nil, right: nil}

    // 输出先序遍历结果
    res := preOrder(root)
    fmt.Println(res) // 输出 [10 5 7 2 12 15]
}

后序遍历算法：

package main
import "fmt"

func postOrder(node *Node) []int {
    res := []int{}
    if node != nil {
        res = append(res, node.val)
        postOrder(node.left)
        postOrder(node.right)
    }
    return res
}

func main() {
    // 创建一棵有3个结点的二叉树
    root := &Node{val: 10, left: nil, right: nil}
    root.left = &Node{val: 5, left: nil, right: nil}
    root.left.left = &Node{val: 3, left: nil, right: nil}
    root.left.right = &Node{val: 7, left: nil, right: nil}
    root.right = &Node{val: 15, left: nil, right: nil}
    root.right.left = &Node{val: 2, left: nil, right: nil}
    root.right.right = &Node{val: 12, left: nil, right: nil}

    // 输出后序遍历结果
    res := postOrder(root)
    fmt.Println(res) // 输出 [15 2 12 7 10 5 3 15]
}

在这里插入图片描述

在这里插入图片描述

智谱清言：

在 Go 语言中，可以使用递归或迭代方法实现树的遍历。以下是先序遍历和后序遍历的递归和迭代算法：

1.先序遍历算法：

递归算法：

func preOrderTraversalRecursive(root *TreeNode) []int {
    if root == nil {
        return []int{}
    }
    result := []int{root.Val}
    result = append(result, preOrderTraversalRecursive(root.Left)...)
    result = append(result, preOrderTraversalRecursive(root.Right)...)
    return result
}

迭代算法：

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

2.后序遍历算法：

递归算法：

func postOrderTraversalRecursive(root *TreeNode) []int {
    if root == nil {
        return []int{}
    }
    result := postOrderTraversalRecursive(root.Left)
    result = append(result, root.Val)
    result = append(result, postOrderTraversalRecursive(root.Right)...)
    return result
}

迭代算法：

func postOrderTraversalIterative(root *TreeNode) []int {
    if root == nil {
        return []int{}
    }
    result := []int{}
    stack := []*TreeNode{root}
    for len(stack) > 0 {
        node := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        result = append(result, node.Val)
        if node.Left != nil {
            stack = append(stack, node.Left)
        }
        if node.Right != nil {
            stack = append(stack, node.Right)
        }
    }
    // Reverse the result array to get post-order traversal
    for i, j := 0, len(result)-1; i < j; i, j = i+1, j-1 {
        result[i], result[j] = result[j], result[i]
    }
    return result
}

以上算法均能在 O(n) 时间内完成树的遍历。

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

通义千问：

这是一个经典的二叉树问题，我们可以使用深度优先搜索（DFS）来解决这个问题。

首先，我们需要定义一个树节点的数据结构：

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

然后，我们分别实现先序遍历和后序遍历的函数：

先序遍历：根 -> 左 -> 右

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

后序遍历：左 -> 右 -> 根

func postorderTraversal(root *TreeNode) []int {
    if root == nil {
        return []int{}
    }
    result := make([]int, 0)
    stack := []*TreeNode{root}
    prev := root
    for len(stack) > 0 {
        node := stack[len(stack)-1]
        if node.Left == nil && node.Right == nil || node == prev {
            result = append([]int{node.Val}, result...)
            prev = node
            stack = stack[:len(stack)-1]
        } else if node.Right != nil {
            stack = append(stack, node.Right)
        } else {
            stack = stack[:len(stack)-1]
            if node.Left != nil {
                stack = append(stack, node.Left)
            }
        }
    }
    return result
}

这两种方法的时间复杂度都是O(n)，其中n是树中节点的数量，因为我们只需要遍历一次所有的节点。空间复杂度也是O(n)，因为在最坏的情况下，我们可能需要将所有的节点都压入栈中。

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

天工：

先序遍历算法：

先序遍历是指先访问根节点，然后依次访问左子树和右子树。在 Go 语言中，可以使用递归实现先序遍历算法。具体实现如下：

// 定义一个树节点结构体
type TreeNode struct {
    Val int
    Left *TreeNode
    Right *TreeNode
}

// 先序遍历算法
func PreorderTraversal(root *TreeNode) {
    if root == nil {
        return
    }
    // 访问当前节点
    fmt.Printf("%d ", root.Val)
    // 递归访问左右子树
    PreorderTraversal(root.Left)
    PreorderTraversal(root.Right)
}

后序遍历算法：

后序遍历是指先访问左子树，然后访问右子树，最后访问根节点。在 Go 语言中，可以使用递归实现后序遍历算法。具体实现如下：

// 定义一个树节点结构体
type TreeNode struct {
    Val int
    Left *TreeNode
    Right *TreeNode
}

// 后序遍历算法
func PostorderTraversal(root *TreeNode) {
    if root == nil {
        return
    }
    // 递归访问左右子树
    PostorderTraversal(root.Left)
    PostorderTraversal(root.Right)
    // 访问当前节点
    fmt.Printf("%d ", root.Val)
}

以上两个算法都是使用递归实现的，时间复杂度为 O(n)，空间复杂度为 O(h)，其中 h 是树的高度。

在这里插入图片描述

在这里插入图片描述

灵小智，代码正常运行：

在Go语言中，可以使用递归的方式实现树的先序遍历和后序遍历算法。下面是相应的实现：

package main

import "fmt"

// 树的节点结构定义
type TreeNode struct {
    Val      int
    Children []*TreeNode
}

// 先序遍历函数
func PreorderTraversal(root *TreeNode) {
    if root == nil {
        return
    }
    fmt.Printf("%d ", root.Val) // 先输出当前节点的值
    for _, child := range root.Children {
        PreorderTraversal(child) // 递归遍历子节点
    }
}

// 后序遍历函数
func PostorderTraversal(root *TreeNode) {
    if root == nil {
        return
    }
    for _, child := range root.Children {
        PostorderTraversal(child) // 递归遍历子节点
    }
    fmt.Printf("%d ", root.Val) // 最后输出当前节点的值
}

func main() {
    // 构建一个示例树
    root := &TreeNode{Val: 1}

    node2 := &TreeNode{Val: 2}
    node3 := &TreeNode{Val: 3}
    node4 := &TreeNode{Val: 4}
    node5 := &TreeNode{Val: 5}

    root.Children = []*TreeNode{node2, node3, node4}
    node2.Children = []*TreeNode{node5}

    // 先序遍历
    fmt.Println("Preorder Traversal:")
    PreorderTraversal(root)
    fmt.Println()

    // 后序遍历
    fmt.Println("Postorder Traversal:")
    PostorderTraversal(root)
    fmt.Println()
}

以上代码通过先序遍历和后序遍历的方式遍历了一棵示例树，并输出了遍历结果。请注意，这里的先序遍历和后序遍历算法的时间复杂度为 O(n)，其中 n 是树中节点的个数。

在这里插入图片描述

在这里插入图片描述

chatgpt，代码正常运行：

在Go语言中，可以使用迭代的方式来实现树的先序遍历和后序遍历，以保证时间复杂度为O(n)。以下是示例代码：

package main

import (
	"fmt"
)

// 树节点结构体
type Node struct {
	Value int
	Left  *Node
	Right *Node
}

// 先序遍历
func PreorderTraversal(root *Node) {
	if root == nil {
		return
	}

	stack := []*Node{root}
	for len(stack) > 0 {
		node := stack[len(stack)-1]
		stack = stack[:len(stack)-1]

		fmt.Printf("%d ", node.Value)

		if node.Right != nil {
			stack = append(stack, node.Right)
		}
		if node.Left != nil {
			stack = append(stack, node.Left)
		}
	}
}

// 后序遍历
func PostorderTraversal(root *Node) {
	if root == nil {
		return
	}

	stack1 := []*Node{root}
	stack2 := []*Node{}
	for len(stack1) > 0 {
		node := stack1[len(stack1)-1]
		stack1 = stack1[:len(stack1)-1]

		stack2 = append(stack2, node)

        // 左子树先入栈
        if node.Left != nil {
            stack1 = append(stack1, node.Left)
        }
        
        // 右子树后入栈 
        if node.Right != nil {  
            stack1 = append(stack1, node.Right)
        }  
    }

    for i := len(stack2)-1; i >= 0; i-- {  
        fmt.Printf("%d ", stack2[i].Value)
    }
}

func main() {
	// 构建一棵树作为示例
	root := &Node{
		Value: 1,
		Left: &Node{
			Value: 2,
			Left: &Node{
				Value: 4,
				Left:  nil,
				Right: nil,
			},
			Right: &Node{
				Value: 5,
				Left:  nil,
				Right: nil,
			},
		},
        Right: &Node{
            Value: 3,
            Left: &Node{
                Value: 6,
                Left:  nil,
                Right: nil,
            },
            Right:nil,   
        },
    }

	fmt.Println("先序遍历结果：")
    PreorderTraversal(root)
    
    fmt.Println("\n后序遍历结果：")
    PostorderTraversal(root)
}

以上代码中，我们使用了两个栈来实现后序遍历。第一个栈用于模拟先序遍历，将右子节点先入栈，然后左子节点入栈。第二个栈用于保存逆向的结果，在第一个栈为空时，将第一个栈中的元素依次弹出并加入到第二个栈中，然后输出即为后序遍历结果。

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

标签：node,144,遍历,TreeNode,nil,VS,文心,root,stack
From： https://www.cnblogs.com/moonfdd/p/17859352.html

相关文章

  • VMware Site Recovery Manager 8.8.0.2 (for vSphere 8.0U2) - 数据中心灾难恢复 (DR)
    VMwareSiteRecoveryManager8.8.0.2(forvSphere8.0U2)-数据中心灾难恢复(DR)请访问原文链接：https://sysin.org/blog/vmware-srm-8/，查看最新版。原创作品，转载请保留出处。作者主页：sysin.org新增功能SiteRecoveryManager8.8.0.2|21NOV2023|Build22795449T......
  • vscode 连接本地虚拟机 Linux 系统
    vscode远程连接本地虚拟机中Linux系统虚拟机配置修改虚拟机的网络设置，将设置->网络->网卡1中的链接方式修改为桥接网卡待验证在网络中选择本地地址转换+端口转发Linux配置Linux安装ssh服务器检查ssh服务器是否已经开启成功systemctlstatussshd如果有......
  • 在VS Code运行C#项目
     目的：运行克隆的C#项目，在命令行里查看运行输出 近日刚刚开始使用VSCode，主要是运行别人的项目测试运算结果，VSCode的配置可以说是一头雾水，搞了好久才成功运行。此文仅作为个人使用踩坑记录，没有什么普适性参考价值，主要是为了自己的不熟练和陌生做一一些没有理论的......
  • JVS-rules规则引擎导出与导入，确保业务连续性的关键
    在复杂的系统环境中，规则和配置的迁移、备份及共享成为了确保业务连续性和一致性的关键过程。不同的环境可能需要相同的规则和配置数据，或者我们可能需要备份这些数据以防万一。JVS规则引擎提供了规则的导出与导入功能，使用户能够在多个环境间轻松转移配置数据。每一条配置数据都有其......
  • 前端开发-vscode必备插件
    1.AutoCloseTag自动闭合html标签2.AutoImport自动引入3.AutoRenameTag自动重命名4.AutoScssStruct4Vue根据vue文件的模板template结构，自动生成对应的scss文件 5.CodeSnap代码生成图片6.codeTour代码向导，适合调......
  • 1、openMVS在ubuntu20.04下的安装
    依赖安装按照这里https://github.com/cdcseacave/openMVS/wiki/Building的安装说明，进行安装，需要说明的是1、Eigen在ubuntu20.04中是3.3.7，它需要3.4版本或者以上的，故需要到这里https://eigen.tuxfamily.org/index.php?title=Main_Page来下载一个3.4版本的，比如.tar.gz；2、VCG库......
  • 文心一言 VS 讯飞星火 VS chatgpt （143）-- 算法导论12.1 3题
    三、用go语言，设计一个执行中序遍历的非递归算法。（提示:一种容易的方法是使用栈作为辅助数据结构;另一种较复杂但比较简洁的做法是不使用栈，但要假设能测试两个指针是否相等。）文心一言，代码正常运行：我们可以使用栈作为辅助数据结构来执行中序遍历的非递归算法。以下是用Go语言实现的代......
  • 文心一言 VS 讯飞星火 VS chatgpt （143）-- 算法导论12.1 3题
    三、用go语言，设计一个执行中序遍历的非递归算法。（提示:一种容易的方法是使用栈作为辅助数据结构;另一种较复杂但比较简洁的做法是不使用栈，但要假设能测试两个指针是否相等。）文心一言，代码正常运行：我们可以使用栈作为辅助数据结构来执行中序遍历的非递归算法。以下是用Go语言实现......
  • 【渗透测试】工具实践之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......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99