Binary Tree Postorder Traversal


#1

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]

Follow up: Recursive solution is trivial, could you do it iteratively?


#2

The below code uses recursion to traverse the binary tree in post order and collect the values at all nodes.

func postorderTraversal(root *TreeNode) []int {
    result := make([]int, 0)
    if root!=nil{helper(root, &result)}
    return result
}

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

#3

The below solution use an explicit stack to traverse the tree in Post Order. The most important part of this problem is to figure out what to do when you are at a node and there exists a right sub tree.

We solve that issue by pushing a node with the node’s value where there exists a right sub tree.

type Stack []*TreeNode		
func (s *Stack) Push(n *TreeNode) {
    *s = append(*s, n)
}
func (s *Stack) Pop() (n *TreeNode) {
    x := s.Len() - 1
    n = (*s)[x]
    *s = (*s)[:x]
    return
}
func (s *Stack) Len() int {
    return len(*s)
}
func (s *Stack) Peek() *TreeNode {
    x := s.Len() - 1
    return (*s)[x]
}

func postorderTraversal(root *TreeNode) []int {
    result := make([]int, 0)
    stack := Stack{}
    cur := root
    for cur!=nil || stack.Len()!=0{
        for cur!=nil{
            stack.Push(cur)
            cur = cur.Left
        }
        
        node := stack.Pop()
        if node.Right!=nil{
            stack.Push(&TreeNode{Val:node.Val})
        } else {
            result = append(result, node.Val)
        }
        
        cur = node.Right
    }
    
    return result
}