Go代码同时使用递归和迭代实现二叉树遍历
package main import ( "fmt" ) type TreeNode struct { Val int Left, Right *TreeNode } type stack []TreeNode func (s stack) Push(t TreeNode) stack { return append(s, t) } func (s stack) Pop() (stack, TreeNode) { return s[:len(s)-1], s[len(s)-1] } func (s stack) IsEmpty() bool { return len(s) == 0 } type queue []TreeNode func (q queue) Enqueue(t TreeNode) queue { return append(q, t) } func (q queue) Dequeue() (queue, TreeNode) { return q[1:], q[0] } func (q queue) IsEmpty() bool { return len(q) == 0 } func PreOrderRecur(t *TreeNode) { if t == nil { return } fmt.Println(t.Val) PreOrderRecur(t.Left) PreOrderRecur(t.Right) } func PreOrder(t *TreeNode) { if t == nil { return } var s stack cur := t for !s.IsEmpty() || cur != nil { if cur != nil { fmt.Println(cur.Val) s = s.Push(*cur) cur = cur.Left } else { s, *cur = s.Pop() cur = cur.Right } } // s = s.Push(*cur) // for !s.IsEmpty() { // s, *cur = s.Pop() // fmt.Println(cur.Val) // if cur.Right != nil { // s = s.Push(*cur.Right) // } // if cur.Left != nil { // s = s.Push(*cur.Left) // } // } } func InOrderRecur(t *TreeNode) { if t == nil { return } InOrderRecur(t.Left) fmt.Println(t.Val) InOrderRecur(t.Right) } func InOrder(t *TreeNode) { if t == nil { return } var s stack cur := t for !s.IsEmpty() || cur != nil { if cur != nil { s = s.Push(*cur) cur = cur.Left } else { s, *cur = s.Pop() fmt.Println(cur.Val) cur = cur.Right } } } func PostOrderRecur(t *TreeNode) { if t == nil { return } PostOrderRecur(t.Left) PostOrderRecur(t.Right) fmt.Println(t.Val) } func PostOrder(t *TreeNode) { if t == nil { return } var s1, s2 stack s1 = s1.Push(*t) cur := t for !s1.IsEmpty() { s1, *cur = s1.Pop() if cur.Left != nil { s1 = s1.Push(*cur.Left) } if cur.Right != nil { s1 = s1.Push(*cur.Right) } s2 = s2.Push(*cur) } for !s2.IsEmpty() { s2, *cur = s2.Pop() fmt.Println(cur.Val) } } func LevelOrder(t *TreeNode) { if t == nil { return } var q queue node := t q = q.Enqueue(*t) for !q.IsEmpty() { q, *node = q.Dequeue() fmt.Println(node.Val) if node.Left != nil { q = q.Enqueue(*node.Left) } if node.Right != nil { q = q.Enqueue(*node.Right) } } }