package BinaryTree
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
func inorderTraversal(root *TreeNode) []int {
return inorderTraversal2(root)
}
// 递归实现
func inorderTraversal1(root *TreeNode) []int {
ret := make([]int, 0)
if root == nil {
return ret
}
leftRet := inorderTraversal1(root.Left)
rightRet := inorderTraversal1(root.Right)
ret = append(ret, leftRet...)
ret = append(ret, root.Val)
ret = append(ret, rightRet...)
return ret
}
type TreeNodeStack []*TreeNode
func (s *TreeNodeStack) Size() int {
return len(*s)
}
func (s *TreeNodeStack) IsEmpty() bool {
return len(*s) == 0
}
func (s *TreeNodeStack) Push(node *TreeNode) {
*s = append(*s, node)
}
func (s *TreeNodeStack) Pop() *TreeNode {
if s.IsEmpty() {
return nil
} else {
node := (*s)[s.Size()-1]
*s = (*s)[:s.Size()-1]
return node
}
}
// 迭代实现
func inorderTraversal2(root *TreeNode) []int {
ret := make([]int, 0)
if root == nil {
return ret
}
s := new(TreeNodeStack)
cur := root
for cur != nil {
s.Push(cur)
cur = cur.Left
}
for !s.IsEmpty() {
node := s.Pop()
ret = append(ret, node.Val)
cur = node.Right
for cur != nil {
s.Push(cur)
cur = cur.Left
}
}
return ret
}