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

2023-11-27
北京
本文字数：6248 字
阅读完需：约 20 分钟

四、用 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 mainimport "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 mainimport "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)}