Binary Tree Preorder Traversal

• LintCode: No.66-Binary Tree Inorder Traversal
• Problem:

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

• Example:

  Given:
       1
      / \
     2   3
    / \
   4   5
  return [1,2,4,5,3].
  

• Analysis:

  Perorder Traversal : visited current Node, Left child,and Right child recursively
  

• Java:

  • Recursive:

    public class Solution {
        public ArrayList<Integer> preorderTraversal(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;
            }
            result.add(node.val);
            traverse(node.left, result);
            traverse(node.right, result);
            return;
        }
    }
    

• Time Complexity:

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