Given a binary tree, return all root-to-leaf paths.
Note: A leaf is a node with no children.
Example:
Input: 1 / \ 2 3 \ 5 Output: ["1->2->5", "1->3"] Explanation: All root-to-leaf paths are: 1->2->5, 1->3
Related Topics:
Tree, Depth-first Search
Since each level we need to copy the path
, it multiplies O(H)
to both the time and space complexity.
// OJ: https://leetcode.com/problems/binary-tree-paths/
// Author: github.com/lzl124631x
// Time: O(NH)
// Space: O(H^2)
class Solution {
private:
vector<string> v;
void preorder(TreeNode *root, string path) {
path += to_string(root->val);
if (!root->left && !root->right) {
v.push_back(path);
return;
}
path += "->";
if (root->left) preorder(root->left, path);
if (root->right) preorder(root->right, path);
}
public:
vector<string> binaryTreePaths(TreeNode* root) {
if (!root) return {};
preorder(root, "");
return v;
}
};
Use vector<TreeNode*>
to store the path visited and construct the string on leaf node.
// OJ: https://leetcode.com/problems/binary-tree-paths/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(H)
class Solution {
private:
vector<TreeNode*> v;
vector<string> ans;
string getString() {
string s = to_string(v[0]->val);
for (int i = 1; i < v.size(); ++i) {
s += "->" + to_string(v[i]->val);
}
return s;
}
void preorder(TreeNode *root) {
v.push_back(root);
if (!root->left && !root->right) ans.push_back(getString());
if (root->left) preorder(root->left);
if (root->right) preorder(root->right);
v.pop_back();
}
public:
vector<string> binaryTreePaths(TreeNode* root) {
if (!root) return {};
preorder(root);
return ans;
}
};