Binary Tree Paths

• LintCode: No.480-Binary Tree Paths
• Problem:

  Given a binary tree, return all root-to-leaf paths.
  

• Example:

  Given the following binary tree:
      1
    /   \
   2     3
    \
     5
  All root-to-leaf paths are:
  [
    "1->2->5",
    "1->3"
  ]
  

• Analysis:

  Visited every node from root to leafs.   
  When the node was a leaf, using a list stored the path and return to this leaf's parent recursively.
  

• Java:

  • Recursive:

    public class Solution {
        public List<String> binaryTreePaths(TreeNode root) {
            List<String> result = new ArrayList<String>();
            if (root == null) {
                return result;
            }
            helper(null, root, result);
            return result;
        }
        public void helper(String prefix, TreeNode root, List<String> result) {
            if (prefix == null) {
                prefix = String.valueOf(root.val); // root node
            } else {
                prefix += "->" + root.val; // not root node
            }
            if (root.left == null && root.right == null) {
                result.add(prefix);
                return;
             } 
            if (root.left != null) {
                helper(prefix, root.left, result);
            } 
            if (root.right != null) {
                helper(prefix, root.right, result);
            }
            return;
        }
    }
    

• Time Complexity:

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