145. 二叉树的后序遍历.md

145. 二叉树的后序遍历

题目传送门

点击这里

解题思路

二叉树三种经典遍历方式的后序遍历方法，后序遍历的顺序是，左->右->根，也同样可以是用dfs和bfs来做，这属于模板类型题。不过这道题的bfs并不好想。

代码

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func postorderTraversal(root *TreeNode) []int {
    // 后续遍历
    // dfs
    var res []int
    var dfs func(*TreeNode)
    dfs = func(node *TreeNode) {
        if node == nil {
            return 
        }
        dfs(node.Left)
        dfs(node.Right)
        res = append(res, node.Val)
    }
    dfs(root)
    return res
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func postorderTraversal(root *TreeNode) []int {
    // bfs
    var res []int
    q := []*TreeNode{}
    // pre用来判定当前右子树的节点是否是上轮已经添加过的节点，是的话可以把当前根节点添加
    var pre *TreeNode
    for root != nil || len(q) > 0 {
        for root != nil {
            q = append(q, root)
            root = root.Left
        }
        // 根取栈内最后一个，向上推进一次
        root = q[len(q)-1]
        q = q[:len(q)-1]
        if root.Right == nil || root.Right == pre {
            // 如果此时根节点的右子树为空，或者此时右子树的节点为上一轮的根节点，那么添加此时的根
            res = append(res, root.Val)
            pre = root
            root = nil
        }else {
            // 否则按照右->根的顺序添加，先将根入队列，然后将根移动到右节点开始计算
            q = append(q, root)
            root = root.Right
        }
    }
    return res
}