Problem

Given a binary tree, return the postorder traversal of its nodes' values.

Example:

Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [3,2,1]

思路

• 先把左边的子节点进栈， 如果左边没有，则右边进栈
• 当栈不为空的时候，
  • 每弹出一个，加到结果
  • 如果这个节点的位置是左节点（stack.peek.left == node), 从对应的右节点开始，重复step1的过程
  • 于是每次所弹出的节点都是按照后序的顺序弹出的

    def postorderTraversal(root: TreeNode): List[Int] = {
        import scala.collection.mutable.{ListBuffer, Stack}
        val res = ListBuffer[Int]()
        val stack = Stack[TreeNode]()
        var node = root
        while (node != null) {
            stack.push(node)
            if (node.left != null)
                node = node.left
            else
                node = node.right
        }
        // 这时候弹出来的第一个节点肯定没有右子节点
        while (stack.nonEmpty) {
            node = stack.pop()
            res.append(node.value)
            if (stack.nonEmpty && node == stack.top.left) {
                node = stack.top.right
                while (node != null) {
                    stack.push(node)
                    if (node.left != null)
                        node = node.left
                    else
                        node = node.right
                }
            }
        }
        res.toList
    }