用 Golang 实现给定一个二叉树,返回它的中序遍历。
输入: [1, null, 2, 3] 1 \ 2 / 3 输出: [1, 3, 2]
package main
import (
"fmt"
)
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
// 递归
func inorderTraversal2(root *TreeNode) []int {
res := make([]int, 0)
doTraversal(root, &res)
return res
}
func doTraversal(root *TreeNode, res *[]int) {
if root == nil {
return
}
doTraversal(root.Left, res)
*res = append(*res, root.Val)
doTraversal(root.Right, res)
}
// 迭代
func inorderTraversal(root *TreeNode) []int {
var res []int
pool := make([]*TreeNode, 0)
pNode := root
for pNode != nil || len(pool) > 0 {
if pNode != nil {
pool = append(pool, pNode)
pNode = pNode.Left
} else {
node := pool[len(pool)-1]
pool = pool[:len(pool)-1]
res = append(res, node.Val)
pNode = node.Right
}
}
return res
}
func main() {
fmt.Println("嗨客网(www.haicoder.net)")
node3 := &TreeNode{
Val:3,
Left:nil,
Right:nil,
}
node2 := &TreeNode{
Val:2,
Left:node3,
Right:nil,
}
node1 := &TreeNode{
Val:1,
Left:nil,
Right:node2,
}
fmt.Println(inorderTraversal2(node1))
}
程序运行后,控制台输出如下:
我们输入了测试用例,输出了正确结果。