Given a binary tree, return all root-to-leaf paths.
For example, given the following binary tree:
1 / 2 3 5
All root-to-leaf paths are:
["1->2->5", "1->3"]
We can not apply inorder traversal here because it only show path from root to leaf node as required. Therefore, we use recursive way.
We consider two situation:
1. Current node is leaf. Add string to result.
2. Current node has children. Go on.
1 /** 2 * Definition for a binary tree node. 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode(int x) { val = x; } 8 * } 9 */ 10 public class Solution { 11 public List<String> binaryTreePaths(TreeNode root) { 12 List<String> result = new ArrayList<String>(); 13 if (root == null) 14 return result; 15 dfs(root, result, new StringBuilder()); 16 return result; 17 } 18 19 private void dfs(TreeNode root, List<String> result, StringBuilder current) { 20 if (root == null) 21 return; 22 if (root.left == null && root.right == null) { 23 current.append(root.val); 24 result.add(current.toString()); 25 return; 26 } 27 28 current.append(root.val); 29 current.append("->"); 30 31 StringBuilder tmp1 = new StringBuilder(current); 32 StringBuilder tmp2 = new StringBuilder(current); 33 if (root.left != null) 34 dfs(root.left, result, tmp1); 35 if (root.right != null) 36 dfs(root.right, result, tmp2); 37 } 38 }
原文：http://www.cnblogs.com/ireneyanglan/p/4847743.html