go 二叉树的非递归遍历 前中后序 leetcode 144 94 145

letterbeezps · · 1167 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

# 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

1167 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传