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

letterbeezps · 2022-05-09 00:54:13 · 1456 次点击 · 预计阅读时间 2 分钟 · 大约8小时之前 开始浏览    
这是一个创建于 2022-05-09 00:54:13 的文章,其中的信息可能已经有所发展或是发生改变。

go 二叉树的非递归遍历

code TreeNode

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

先序遍历 中左右

code

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

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

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

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