Time: O(n), Space: O(h)
Use string:
/**
* 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> res = new ArrayList<>();
if (root == null) {
return res;
}
binaryTreePaths(root, "", res);
return res;
}
private void binaryTreePaths(TreeNode root, String s, List<String> res) {
if (root == null) {
return;
}
if (root.left == null && root.right == null) {
s += root.val;
res.add(s);
return;
}
binaryTreePaths(root.left, s + root.val + "->", res);
binaryTreePaths(root.right, s + root.val + "->", res);
}
}
Use stringbuilder:
/**
* 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> res = new ArrayList<>();
if (root == null) {
return res;
}
StringBuilder sb = new StringBuilder();
binaryTreePaths(root, sb, res);
return res;
}
private void binaryTreePaths(TreeNode root, StringBuilder sb, List<String> res) {
if (root == null) {
return;
}
int length = sb.length();
if (root.left == null && root.right == null) {
sb.append(root.val);
res.add(sb.toString());
sb.setLength(length);
return;
}
sb.append(root.val).append("->");
binaryTreePaths(root.left, sb, res);
binaryTreePaths(root.right, sb, res);
sb.setLength(length);
}
}