My concise JAVA DFS solution


  • 17

    Explanation

    This is just a classic problem to use depth first search algorithm.

    public List<String> binaryTreePaths(TreeNode root) {
        ArrayList<String> res = new ArrayList<String>();        
        DFS(root, "", res);
        return res;        
    }
    	
    public void DFS(TreeNode root, String solution, ArrayList<String> res) {
    	if (root == null) return;    	
    	if (root.left==null && root.right==null) res.add(solution + root.val);
    	DFS(root.left, solution + root.val + "->", res);    	
    	DFS(root.right, solution + root.val + "->", res);    	    	
    }

  • 0
    Y

    Same idea here.

    public class Solution {
    	public List<String> binaryTreePaths(TreeNode root) {
    		List<String> res = new ArrayList<String>();
    		String onepath = "";
    		return helper(res, onepath, root);		
    	}
    	
    	public List<String> helper(List<String> result, String path, TreeNode root) {
    		if(root.left==null && root.right==null){
    			path += root.val;
    			result.add(new String(path));
    		}
    		
    		path = path + root.val+"->";
    		if(root.left!=null)
    			helper(result, path, root.left);
    		if(root.right!=null)
    			helper(result, path, root.right);	
    		return result;
    		
    	}
    }

Log in to reply
 

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