三、用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