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