Dare2Solve
Given a binary tree, the task is to return all root-to-leaf paths as a list of strings. Each path should be formatted as a string where nodes are joined by "->"
.
The problem can be approached by recursively traversing the tree. As we move from the root to the leaves, we can build a path string and add it to the result once we reach a leaf node. The key insight is that each leaf node represents the end of a unique path from the root.
Recursive Traversal:
Path Construction:
"->"
if it’s not the end of the path.Edge Cases:
null
), the result should be an empty list.O(N)
, where N
is the number of nodes in the tree. We visit each node exactly once during the traversal.
O(H)
, where H
is the height of the tree. This is the maximum depth of the recursion stack. In the worst case, the space complexity could be O(N)
if the tree is skewed (i.e., all nodes are on one side).
class Solution {
public:
vector<string> binaryTreePaths(TreeNode* root) {
vector<string> res;
if (!root) return res;
function<void(string, TreeNode*)> path = [&](string p, TreeNode* node) {
if (node && !node->left && !node->right) {
string pathV = p.empty() ? to_string(node->val) : p + "->" + to_string(node->val);
res.push_back(pathV);
return;
} else if (node) {
string pathV = p.empty() ? to_string(node->val) : p + "->" + to_string(node->val);
if (node->left) {
path(pathV, node->left);
}
if (node->right) {
path(pathV, node->right);
}
}
};
path("", root);
return res;
}
};
class Solution:
def binaryTreePaths(self, root: TreeNode) -> List[str]:
res = []
if not root:
return res
def path(p: str, node: TreeNode):
if node and not node.left and not node.right:
pathV = f"{p}->{node.val}" if p else str(node.val)
res.append(pathV)
elif node:
pathV = f"{p}->{node.val}" if p else str(node.val)
if node.left:
path(pathV, node.left)
if node.right:
path(pathV, node.right)
path("", root)
return res
class Solution {
public List<String> binaryTreePaths(TreeNode root) {
List<String> res = new ArrayList<>();
if (root == null) return res;
path("", root, res);
return res;
}
private void path(String p, TreeNode node, List<String> res) {
if (node != null && node.left == null && node.right == null) {
String pathV = p.isEmpty() ? String.valueOf(node.val) : p + "->" + node.val;
res.add(pathV);
} else if (node != null) {
String pathV = p.isEmpty() ? String.valueOf(node.val) : p + "->" + node.val;
if (node.left != null) {
path(pathV, node.left, res);
}
if (node.right != null) {
path(pathV, node.right, res);
}
}
}
}
var binaryTreePaths = function (root) {
let res = [];
let path = function (p, node) {
if (node && !node.left && !node.right) {
let pathV = p ? p + "->" + node.val : String(node.val);
res.push(pathV);
return;
} else if (node) {
let pathV = p ? p + "->" + node.val : String(node.val);
if (node.left) {
path(pathV, node.left)
}
if (node.right) {
path(pathV, node.right)
}
} else {
return;
}
}
path("", root);
return res;
};