Binary Tree Postorder Traversal

• LintCode: No.68- Binary Tree Postorder Traversal
• Problem:

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

• Example:

  Given binary tree {1,#,2,3},
    1
     \
      2
     /
    3 
  return [3,2,1]].
  

• Analysis:

  Postorder Traversal : visited Left child, Right child, and current node recursively
  

• Java:

  • Recursive:

    public class Solution {
        public ArrayList<Integer> Postorder Traversal(TreeNode root) {
            ArrayList<Integer> result = new ArrayList<Integer>();
            traverse(root, result);
            return result;
        }
        public void traverse(TreeNode node, ArrayList<Integer> result) {
            if (node == null) {
                return;
            }
            traverse(node.left, result);
            traverse(node.right, result);
            result.add(node.val);
            return;
        }
    }
    

• Time Complexity:

  • O(n), n is the number of nodes