Binary Tree Paths DFS java solution


  • 3
    V

    public class Solution {

    public List<String> binaryTreePaths(TreeNode root) {
    
        List<String> ret = new ArrayList<String>();
        
        if(root == null){
            return ret;
        }
        
        dfs(root, new StringBuilder(), ret);
        
        return ret;
    }
    
    public void dfs(TreeNode root, StringBuilder sb, List<String> ret){
    
       if(root.left == null && root.right == null){
           sb.append(root.val);
           ret.add(sb.toString());
           return;
       }
        
       sb.append(root.val);
       sb.append("->");
       
       if(root.left != null){
           dfs(root.left, new StringBuilder(sb), ret);
       }
       
       if(root.right != null){
           dfs(root.right, new StringBuilder(sb), ret);
       }
    }
    

    }


  • 0
    X
    This post is deleted!

  • 0
    X

    Hi , can you tell me why I need to add new StringBuilder(sb) instead of just using sb in the dfs(root.left, new StringBuilder(sb), ret);?? Thank you!


  • 0
    S

    because when the root has two children, it should comes out two StringBuilder all base on the original root StringBuilder, for convenience, we just create a new StringBuilder when root has a child.

    hope this would help you.


  • 0
    M

    You could try this service for a full solution http://www.helpwithprogramming.com/


Log in to reply
 

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