257. Binary Tree Paths

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

For example, given the following binary tree:

   1
 /   \
2     3
 \
  5

All root-to-leaf paths are:

["1->2->5", "1->3"]

Analysis:

Recursive pre-order traverse, at each visit:

use string builder to store string so far, if node is leaf, use toString on StringBuilder and add it to returnList

be careful of end of each resursion, when deleting current node from string, need to delete based on the length of the value.

Complexity:

Time: o(n) - all node need to be visited once

Space: O(logn) - height of the tree, depth of recursion

Code:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {

    List<String> returnList = new LinkedList<String>();
    public List<String> binaryTreePaths(TreeNode root) {
        if(root == null)
        {
            return returnList;
        }

        StringBuilder sb = new StringBuilder();
        //sb.append(Integer.toString(root.val) + "->");
        traverse(root, sb);
        return returnList;

    }

    private void traverse(TreeNode root, StringBuilder sb)
    {
        if(root == null)
        {
            return;
        }

        String str = Integer.toString(root.val);
        sb.append(str);

        if(root.left == null && root.right == null)
        {
            returnList.add(sb.toString());
            sb.delete(sb.length()-str.length(), sb.length());
            return;
        }
        else
        {
            sb.append("->");
        }

        traverse(root.left, sb);
        traverse(root.right, sb);
        sb.delete(sb.length()-2-str.length(), sb.length());
    }



}