go 二叉树的非递归遍历

code TreeNode

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

先序遍历 中左右

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
}

中序遍历 左中右

于先序遍历一样先将左边节点入栈

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
}

后续遍历 左右中

注意：“左右中”就是“中右左”的逆序，而按照“中右左” 顺序遍历二叉树的方思路和 先序“中左右”一样

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]
    }
}