PreOrder
recursive
package main
import "fmt"
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 main() {
/*
10
/
20 30
/
40 50 60
/
70
*/
root := &TreeNode{10, nil, nil}
root.Left = &TreeNode{20, nil, nil}
root.Right = &TreeNode{30, nil, nil}
root.Left.Left = &TreeNode{40, nil, nil}
root.Left.Right = &TreeNode{50, nil, nil}
root.Right.Right = &TreeNode{60, nil, nil}
root.Left.Left.Left = &TreeNode{70, nil, nil}
fmt.Println("Preorder Traversal - Recursive Solution : ")
preorderTraversal(root)
}
Iterative
package main
import "fmt"
type TreeNode struct {
val int
Left *TreeNode
Right *TreeNode
}
func preorderTraversal(root *TreeNode) {
if root == nil {
return
}
stack := make([]*TreeNode, 0)
for root != nil || len(stack) != 0 {
for root != nil {
fmt.Println(root.val)
stack = append(stack, root)
root = root.Left
}
v := stack[len(stack)-1]
stack = stack[:len(stack)-1]
root = v.Right
}
}
func main() {
/*
10
/
20 30
/
40 50 60
/
70
*/
root := &TreeNode{10, nil, nil}
root.Left = &TreeNode{20, nil, nil}
root.Right = &TreeNode{30, nil, nil}
root.Left.Left = &TreeNode{40, nil, nil}
root.Left.Right = &TreeNode{50, nil, nil}
root.Right.Right = &TreeNode{60, nil, nil}
root.Left.Left.Left = &TreeNode{70, nil, nil}
fmt.Println("Preorder Traversal - Iterative Solution : ")
preorderTraversal(root)
}
另一种写法
func preorderTraversal(root *TreeNode) {
if root == nil {
return
}
stack := make([]*TreeNode, 0)
stack = append(stack, root)
for len(stack) != 0 {
node := stack[len(stack)-1]
stack = stack[:len(stack)-1]
fmt.Println(node.val)
if node.Right != nil {
stack = append(stack, node.Right)
}
if node.Left != nil {
stack = append(stack, node.Left)
}
}
}
InOrder
Iterative
func inorderTraverse(root *TreeNode) {
if root == nil {
return
}
stack := make([]*TreeNode, 0)
for root != nil || len(stack) != 0 {
for root != nil {
stack = append(stack, root)
root = root.Left
}
node := stack[len(stack)-1]
stack = stack[:len(stack)-1]
fmt.Println(node.val)
root = node.Right
}
}
PostOrder
Iterative
func postorderTraversal(root *TreeNode) {
if root == nil {
return
}
stack := make([]*TreeNode, 0)
var lastNode *TreeNode
for root != nil || len(stack) != 0 {
for root != nil {
stack = append(stack, root)
root = root.Left
}
node := stack[len(stack)-1]
if node.Right == nil || node.Right == lastNode {
stack = stack[:len(stack)-1]
lastNode = node
fmt.Println(node.val)
} else {
root = node.Right
}
}
}