Golang二叉树中序遍历

题目

Golang 实现给定一个二叉树,返回它的中序遍历。

示例1

输入: [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)) }

程序运行后,控制台输出如下:

18_golang二叉树中序遍历.png

我们输入了测试用例,输出了正确结果。