https://leetcode.com/problems/binary-tree-paths/
Problem Statement:
Given a binary tree, return all root-to-leaf paths.
Note: A leaf is a node with no children.
Examples
1:
Input:
1
/ \
2 3
\
5
Output: ["1->2->5", "1->3"]
Explanation: All root-to-leaf paths are: 1->2->5, 1->3
Idea:
The most intuitive way is to use a recursion here. One is going through the tree by considering at each step the node itself and its children. If node is not a leaf, one extends the current path by a node value and calls recursively the path construction for its children. If node is a leaf, one closes the current path and adds it into the list of paths.
Solution:
class Solution {
public:
void findPath(TreeNode * root, vector<string> &paths, vector<int> &path) {
if(root == nullptr) return;
path.push_back(root->val);
if(root->left == nullptr && root->right == nullptr) {
string res = std::to_string(path[0]);
for(unsigned i = 1; i < path.size(); ++i) {
res += "->" + std::to_string(path[i]);
}
paths.push_back(res);
}
findPath(root->left, paths, path);
findPath(root->right, paths, path);
path.pop_back();
}
vector<string> binaryTreePaths(TreeNode* root) {
vector<string> paths;
vector<int> path;
findPath(root, paths, path);
return paths;
}
};
Comments
Nothing yet.