迭代中序遍历二叉树，需要使用一个变量表示左子树是否已经被访问，还需要一个队列保存当前路径中还未访问的节点。如果当前节点的左子树不为空且还未访问，则直接将左子树添加到队列中。如果当前节点的左子树为空或者已经访问过，则可以访问当前节点以及其右子树。
代码如下
package main
import "fmt"
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
LVisited bool
}
func TreeIter(root *TreeNode) string {
r := ""
if root == nil {
return r
}
q := []*TreeNode{root}
for len(q) > 0 {
n := q[len(q)-1]
if n.Left != nil && !n.LVisited {
n.LVisited = true
q = append(q, n.Left)
} else {
r += fmt.Sprintf("(%d)", n.Val)
q = q[:len(q)-1]
if n.Right != nil {
q = append(q, n.Right)
}
}
}
return r
}
func main() {
cs := []*TreeNode{
{
Val: 1,
Left: &TreeNode{
Val: 2,
Left: &TreeNode{
Val: 4,
},
},
Right: &TreeNode{
Val: 3,
},
},
{
Val: 1,
Left: &TreeNode{
Val: 2,
Right: &TreeNode{Val: 4},
},
Right: &TreeNode{Val: 3},
},
}
for i := range cs {
fmt.Printf("test %d: result: %s", i, TreeIter(cs[i]))
}
}
