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

  1. 输入: [1,null,2,3]  
  2.    1
  3.     \
  4.      2
  5.     /
  6.    3 
  7. 输出: [3,2,1]

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

解法一：递归

  1. func postorderTraversal(root *TreeNode) []int {
  2.     res := []int{}
  3.     var postOrder func(root *TreeNode)
  4.     postOrder = func(root *TreeNode) {
  5.         if root == nil {
  6.             return
  7.         }
  8.         postOrder(root.Left)
  9.         postOrder(root.Right)
  10.         res = append(res, root.Val)
  11.     }
  12.     postOrder(root)
  13.     return res
  14. }

解法二：投机取巧

后序是：左右根
前序是：根左右
把前序改造为 根右左 ，将最后结果逆序即可。

func postorderTraversal(root *TreeNode) []int {
    res := []int{}
    var postOrder func(root *TreeNode)
    postOrder = func(root *TreeNode) {
        if root == nil {
            return
        }
        postOrder(root.Right)
        postOrder(root.Left)
        res = append(res, root.Val)
    }
    postOrder(root)
       left, right := 0, len(res)-1

    for left < right {
        res[left], res[right] = res[right], res[left]
        left++
        right--
    }
    return res
}

func postorderTraversal(root *TreeNode) []int {
    res := []int{}
    stack := []*TreeNode{}
    top := root
    for len(stack) > 0 || top != nil {
        for top != nil {
            res = append(res, top.Val)
            stack = append(stack, top.Left)
            top = top.Right
        }
        top, stack = stack[len(stack)-1], stack[:len(stack)-1]
    }
    left, right := 0, len(res)-1

    for left < right {
        res[left], res[right] = res[right], res[left]
        left++
        right--
    }
    return res
}

解法三：迭代

func postorderTraversal(root *TreeNode) []int {
    res := []int{}
    stack := []*TreeNode{}
    top := root
    var prev *TreeNode
    for len(stack) > 0 || top != nil {
        for top != nil {
            stack = append(stack, top)
            top = top.Left
        }
        top, stack = stack[len(stack)-1], stack[:len(stack)-1]
        // 不存在有节点的和右节点是前面遍历过的
        if top.Right == nil || top.Right == prev {
            res = append(res, top.Val)
            // 实际上这个 prev 是上一个遍历的节点，或者说是上一个被输出的节点
            prev = top
            top = nil
        } else {
            stack = append(stack, top)
            top = top.Right
        }
    }

    return res
}