分享
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。
# go 二叉树的非递归遍历
## code TreeNode
```go
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
```
## 先序遍历 中左右
### code
```go
func preorderTraversal(root *TreeNode) []int {
if root == nil {
return []int{}
}
res := []int{}
stack := []*TreeNode{}
cur := root
for len(stack) > 0 || cur != nil {
if cur != nil {
res = append(res, cur.Val)
stack = append(stack, cur)
cur = cur.Left
} else {
cur = stack[len(stack)-1]
stack = stack[:len(stack)-1]
cur = cur.Right
}
}
return res
}
```
## 中序遍历 左中右
于先序遍历一样先将左边节点入栈
### code
```go
func inorderTraversal(root *TreeNode) []int {
if root == nil {
return []int{}
}
res := []int{}
stack := []*TreeNode{}
cur := root
for len(stack) > 0 || cur != nil {
for cur != nil {
stack = append(stack, cur)
cur = cur.Left
}
if len(stack) > 0 {
cur = stack[len(stack)-1]
res = append(res, cur.Val)
stack = stack[:len(stack)-1]
cur = cur.Right
}
}
return res
}
```
## 后续遍历 左右中
**注意**:"左右中"就是"中右左"的逆序,而按照"中右左" 顺序遍历二叉树的方思路和 先序"中左右"一样
### code
```go
func postorderTraversal(root *TreeNode) []int {
if root == nil {
return []int{}
}
res := []int{}
stack := []*TreeNode{}
cur := root
for len(stack) > 0 || cur != nil {
if cur != nil {
res = append(res, cur.Val)
stack = append(stack, cur)
cur = cur.Right
} else {
cur = stack[len(stack)-1]
stack = stack[:len(stack)-1]
cur = cur.Left
}
}
reverse(res)
return res
}
func reverse(res []int) {
for i, j := 0, len(res)-1; i < j; i, j = i+1, j-1 {
res[i], res[j] = res[j], res[i]
}
}
```
有疑问加站长微信联系(非本文作者))
入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889
关注微信1887 次点击
上一篇:什么是中间件
下一篇: 可观测性:运维风向标!
添加一条新回复
(您需要 后才能回复 没有账号 ?)
- 请尽量让自己的回复能够对别人有帮助
- 支持 Markdown 格式, **粗体**、~~删除线~~、
`单行代码` - 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
- 图片支持拖拽、截图粘贴等方式上传