|
| 1 | +packageeasy; |
| 2 | + |
| 3 | +importjava.util.ArrayList; |
| 4 | +importjava.util.List; |
| 5 | + |
| 6 | +importutils.CommonUtils; |
| 7 | +importclasses.TreeNode; |
| 8 | + |
| 9 | +/**257. Binary Tree Paths Question Editorial Solution My Submissions |
| 10 | +Total Accepted: 59117 |
| 11 | +Total Submissions: 191659 |
| 12 | +Difficulty: Easy |
| 13 | +Given a binary tree, return all root-to-leaf paths. |
| 14 | +
|
| 15 | +For example, given the following binary tree: |
| 16 | +
|
| 17 | + 1 |
| 18 | + / \ |
| 19 | +2 3 |
| 20 | + \ |
| 21 | + 5 |
| 22 | +All root-to-leaf paths are: |
| 23 | +
|
| 24 | +["1->2->5", "1->3"] |
| 25 | +*/ |
| 26 | +publicclassBinaryTreePaths { |
| 27 | +//a very typical/good question to test your recursion/dfs understanding. |
| 28 | +publicList<String>binaryTreePaths_more_concise(TreeNoderoot) { |
| 29 | +List<String>paths =newArrayList<String>(); |
| 30 | +if(root ==null)returnpaths; |
| 31 | +dfs(root,paths,""); |
| 32 | +returnpaths; |
| 33 | + } |
| 34 | + |
| 35 | +privatevoiddfs(TreeNoderoot,List<String>paths,Stringpath) { |
| 36 | +if(root.left ==null &&root.right ==null){ |
| 37 | +paths.add(path +root.val); |
| 38 | +return; |
| 39 | + } |
| 40 | +path +=root.val +"->"; |
| 41 | +if(root.left !=null)dfs(root.left,paths,path); |
| 42 | +if(root.right !=null)dfs(root.right,paths,path); |
| 43 | + } |
| 44 | + |
| 45 | +publicstaticvoidmain(String...strings){ |
| 46 | +BinaryTreePathstest =newBinaryTreePaths(); |
| 47 | +TreeNoderoot =newTreeNode(1); |
| 48 | +root.left =newTreeNode(2); |
| 49 | +root.left.right =newTreeNode(5); |
| 50 | +root.right =newTreeNode(3); |
| 51 | +List<String>res =test.binaryTreePaths(root); |
| 52 | +CommonUtils.print(res); |
| 53 | + } |
| 54 | + |
| 55 | +publicList<String>binaryTreePaths(TreeNoderoot) { |
| 56 | +List<String>paths =newArrayList<String>(); |
| 57 | +dfs(root,paths,newStringBuilder()); |
| 58 | +returnpaths; |
| 59 | + } |
| 60 | + |
| 61 | +privatevoiddfs(TreeNoderoot,List<String>paths,StringBuildersb) { |
| 62 | +if(root ==null)return; |
| 63 | +if(root.left ==null &&root.right ==null){ |
| 64 | +sb.append(root.val); |
| 65 | +paths.add(sb.toString()); |
| 66 | +return ; |
| 67 | + } |
| 68 | +sb.append(root.val +"->"); |
| 69 | +Stringcurr =sb.toString(); |
| 70 | +if(root.left !=null)dfs(root.left,paths,sb); |
| 71 | +sb.setLength(0); |
| 72 | +sb.append(curr); |
| 73 | +if(root.right !=null)dfs(root.right,paths,sb); |
| 74 | + } |
| 75 | +} |