145. 二叉树的后序遍历

题目#

给定一个二叉树，返回它的后序遍历。

示例:

输入: [1,null,2,3]
   1
    \
     2
    /
   3

输出: [3,2,1]

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

思路#

同样，递归很简单。

相信大家在最初学习二叉树的三种遍历时，便听说过“二叉树的后序遍历非递归解法非常麻烦”这一说法，这一说法所言非虚。

但我们可以换一个思路，后序遍历的顺序是 左-右-根，那我们可以做一个 根-右-左 的遍历，最后做一个 reverse 即可得到后序遍历的结果。

根-右-左 的遍历顺序类似于先序遍历。

代码#

递归#

func postorderTraversal(root *TreeNode) []int {
    res := []int{}
    postorder(root, &res)
    return res
}

func postorder(root *TreeNode, res *[]int) {
    if root != nil {
        postorder(root.Left, res)
        postorder(root.Right, res)
        *res = append(*res, root.Val)
    }
}

迭代#

func postorderTraversal(root *TreeNode) []int {
    res := []int{}
    if root == nil {
        return res
    }

    stack := []*TreeNode{}
    stack = append(stack, root)
    for len(stack) != 0 {
        node := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        res = append(res, node.Val)
        if node.Left != nil {
            stack = append(stack, node.Left)
        }
        if node.Right != nil {
            stack = append(stack, node.Right)
        }
    }
    reverse(&res)
    return res
}

func reverse(arr *[]int) {
    i, j := 0, len(*arr)-1
    for i < j {
        (*arr)[i], (*arr)[j] = (*arr)[j], (*arr)[i]
        i++
        j--
    }
}