Binary Tree Paths

Problem Description

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"]

Solution
I. Java Solution

view plainprint?

1. /** 
2.  * Definition for a binary tree node. 
3.  * public class TreeNode { 
4.  *     int val; 
5.  *     TreeNode left; 
6.  *     TreeNode right; 
7.  *     TreeNode(int x) { val = x; } 
8.  * } 
9.  */  
10. public class Solution {  
11.     public List<String> binaryTreePaths(TreeNode root) {  
12.         List<String> result = new ArrayList<String>();  
13.           
14.         if(root == null) return result;  
15.         LinkedList<TreeNode> path = new LinkedList<TreeNode>();  
16.           
17.         path.push(root);  
18.           
19.         TreeNode temp;  
20.         while(!path.isEmpty()){  
21.             temp = path.peek();  
22.             if(temp.left != null){  
23.                 path.push(temp.left);  
24.             }else if(temp.right != null){  
25.                 path.push(temp.right);  
26.             }else{  
27.                 result.add(listToString(path));  
28.                 temp = path.pop();  
29.                 while(!path.isEmpty()){  
30.                     if(path.peek().left == temp  
31.                         && path.peek().right!=null){  
32.                         path.push(path.peek().right);  
33.                         break;  
34.                     }  
35.                     temp = path.pop();  
36.                 }  
37.             }  
38.               
39.         }  
40.       
41.         return result;  
42.     }  
43.       
44.     public String listToString(LinkedList<TreeNode> path){  
45.         ListIterator<TreeNode> iterator = path.listIterator(path.size());  
46.         StringBuilder builder = new StringBuilder();  
47.         builder.append(iterator.previous().val);  
48.         while(iterator.hasPrevious()){  
49.             builder.append("->" + iterator.previous().val);  
50.         }  
51.         return builder.toString();  
52.     }  
53. }  

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> result = new ArrayList<String>();
        
        if(root == null) return result;
        LinkedList<TreeNode> path = new LinkedList<TreeNode>();
        
        path.push(root);
        
        TreeNode temp;
        while(!path.isEmpty()){
            temp = path.peek();
            if(temp.left != null){
                path.push(temp.left);
            }else if(temp.right != null){
                path.push(temp.right);
            }else{
                result.add(listToString(path));
                temp = path.pop();
                while(!path.isEmpty()){
                    if(path.peek().left == temp
                        && path.peek().right!=null){
                        path.push(path.peek().right);
                        break;
                    }
                    temp = path.pop();
                }
            }
            
        }
    
        return result;
    }
    
    public String listToString(LinkedList<TreeNode> path){
        ListIterator<TreeNode> iterator = path.listIterator(path.size());
        StringBuilder builder = new StringBuilder();
        builder.append(iterator.previous().val);
        while(iterator.hasPrevious()){
            builder.append("->" + iterator.previous().val);
        }
        return builder.toString();
    }
}