My solution, little long but


  • 0
    G
    /**
     * 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> retList = new ArrayList<String>();
        	StringBuffer sb = new StringBuffer();
            if(root==null) {
            	return retList;
            }
        	
            if(root.left==null && root.right==null) {
            	sb.append(root.val);
            	retList.add(sb.toString());
            	return retList;
            }
            
            List<TreeNode> arList = new ArrayList<TreeNode>();
            Map <Integer,List> keyMap = new HashMap<Integer,List>();
            arList.add(root);
            keyMap.put(new Integer(1),arList);
            helper(arList, root);
            Set <List> listSet = new HashSet<List>();
            
            for(int i=arList.size()-1;i>=0;i--) {
            	TreeNode node = arList.get(i);
            	if(node.left==null && node.right==null) {
            		List <String> pathList = new ArrayList<String>();
            		pathList.add(String.valueOf(node.val));
            		listSet.add(pathList);
            		arList.remove(i);
            		//i++;
            	}
            }
    
          
            for(int i=arList.size()-1;i>=0;i--) {
            	TreeNode node = arList.get(i);
            	familyUnion(node, listSet);
            }        
    
            
            Iterator<List> iter = listSet.iterator();
            sb.delete(0, sb.length());
            while(iter.hasNext()) {
            	List val = iter.next();
            	for(int i=0;i<val.size();i++) {
            		if(i==val.size()-1) {
            			sb.append(val.get(i));
            		}
            		else {
            			sb.append(val.get(i));
            			sb.append("->");
            		}        		
            	}
            	retList.add(sb.toString());
            	sb.delete(0, sb.length());
            }
            
            return retList;
        }	
    	
        
        public void familyUnion(TreeNode father, Set kids) {
        	boolean condition1 = false;
        	boolean condition2 = false;
        	Iterator <List> iter = kids.iterator();
        	while(iter.hasNext()) {
        		List <String> kid = iter.next();
        		for(int k=0;k<kid.size();k++) {
        			String val = kid.get(k);
        			//check if curren node is father
        			if(father.left!=null   && String.valueOf(father.left.val).equals(val)) {
        				String valueTobeAdded = String.valueOf(father.val);
        				// add father 
        				String temp = val;
        				kid.set(k, valueTobeAdded);
        				kid.add(temp); 
        				// got your father so go back
        				break;
        			}
        			if(father.right!=null  && String.valueOf(father.right.val).equals(val)) {
        				String valueTobeAdded = String.valueOf(father.val);
        				// add father
        				String temp = val;
        				kid.set(k, valueTobeAdded);
        				kid.add(temp);
        				// got your father so go back
        				break;    				
        			}       			    			
        		}
        	}
        }
        
        
        public void helper( List arList ,TreeNode node) {
        	
        	
        	if(node.left!=null) {
        		arList.add(node.left);    	
        	}
        	
            	if(node.right!=null) {
            		arList.add(node.right);                		            		
        	}
        	
            	if(node.left!=null) {
            		helper(arList, node.left);
            	}
            	if(node.right!=null) {
            		helper(arList, node.right);
            	}
        		
        }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.