/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<String> binaryTreePaths(TreeNode root) {
// List<String> ans = new ArrayList<>();
// if (root == null) {
// return ans;
// }
// // 如果是叶子结点就加入到 ans 结果集中
// if (root.left == null && root.right == null) {
// ans.add(Integer.toString(root.val));
// return ans;
// }
// // 创建左子树结点集合
// List<String> leftPaths = binaryTreePaths(root.left);
// for (String s : leftPaths) {
// // 先将该结点加入到字符串中
// StringBuilder sb = new StringBuilder(Integer.toString(root.val));
// sb.append("->");
// sb.append(s);
// ans.add(sb.toString());
// }
// // 创建右子树结点集合
// List<String> rightPaths = binaryTreePaths(root.right);
// for (String s : rightPaths) {
// StringBuilder sb = new StringBuilder(Integer.toString(root.val));
// sb.append("->");
// sb.append(s);
// ans.add(sb.toString());
// }
// return ans;
LinkedList<String> paths = new LinkedList();
construct_paths(root, "", paths);
return paths;
}
public void construct_paths(TreeNode root, String path, LinkedList<String> paths) {
if (root != null) {
path += Integer.toString(root.val);
if ((root.left == null) && (root.right == null)) // 当前节点是叶子节点
paths.add(path); // 把路径加入到答案中
else {
path += "->"; // 当前节点不是叶子节点，继续递归遍历
construct_paths(root.left, path, paths);
construct_paths(root.right, path, paths);
}
}
}
}
