文心一言 VS 讯飞星火 VS chatgpt （143）-- 算法导论12.1 3题
生活随笔
收集整理的這篇文章主要介紹了
文心一言 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 算法，它不需要額外的棧空間，但需要對指針進行特殊處理。在此不再贅述。
總結
以上是生活随笔為你收集整理的文心一言 VS 讯飞星火 VS chatgpt （143）-- 算法导论12.1 3题的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Udacity机器人软件工程师课程笔记（
- 下一篇： Java开发者的Python快速进修指南