My Java Solution


  • 0
    G

    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);
    	}
    

    }

    /**

    • @param args
      */

Log in to reply
 

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