480.Binary Tree Paths

1.Description(Easy)

Given a binary tree, return all root-to-leaf paths.

Example

Given the following binary tree:

   1
 /   \
2     3
 \
  5

All root-to-leaf paths are:

[
  "1->2->5",
  "1->3"
]

2.Code

先把root的值放进去，之后每次dfs可以直接在前面加上“->”.

dfs先判断如果是leaf,就直接把path加入result，在进行左右子树的dfs.

public List<String> binaryTreePaths(TreeNode root){
     List<String> result=new ArrayList<String>();
     if(root==null){
         return result;
     }
     String path=String.valueOf(root.val);
     dfs(root,path,result);
     return result;
 }
 public void dfs(TreeNode root,String path,List<String> result){
     if(root==null){
         return;
     }
     if(root.left==null && root.right==null){
         result.add(path);
         return;
     }
     if(root.left!=null){
         String newpath=path+"->"+String.valueOf(root.left.val);
         dfs(root.left,newpath,result);
     }
     if(root.right!=null){
         String newpath=path+"->"+String.valueOf(root.right.val);
         dfs(root.right,newpath,result);
     }
 }