Tree - 145. Binary Tree Postorder Traversal

/**

 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

/* // recursive
func postorderTraversal(root *TreeNode) []int {
    var res []int
    
    recursive(root, &res)
    
    return res
}


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

// iteratively
func postorderTraversal(node *TreeNode) []int {

    var res []int 
    var stack []*TreeNode
    var visited *TreeNode
    
    for node != nil || len(stack) != 0 {
        for node != nil {
            stack = append(stack, node)
            node = node.Left
        }
        
        // ·ÃÎÊÕ»¶¥ÔªËØ
        node = stack[len(stack) - 1]
        
        if node.Right != nil && node.Right != visited {
            node = node.Right
        } else {
            // ¸¸½ÚµãµÄÓÒ×ÓÊ÷±»·ÃÎʹýÁË£¬¸¸½Úµã³öÕ»
            stack = stack[:len(stack) - 1]
            res = append(res, node.Val)
            visited = node
            node = nil  // ±£Ö¤²»»áÔÙ±»ÈëÕ»
        }
    }
    
    return res
}