Given a binary tree, return all root-to-leaf paths.
Example
Given the following binary tree:
1
/ \
2 3
\
5
All root-to-leaf paths are:
[
"1->2->5",
"1->3"
]
LeetCode上的原题，请参见我之前的博客Binary Tree Paths。
解法一：
class Solution {
public:
/**
* @param root the root of the binary tree
* @return all root-to-leaf paths
*/
vector<string> binaryTreePaths(TreeNode* root) {
vector<string> res;
if (root) helper(root, "", res);
return res;
}
void helper(TreeNode *node, string out, vector<string> &res) {
out += to_string(node->val);
if (!node->left && !node->right) {
res.push_back(out);
} else {
if (node->left) helper(node->left, out + "->", res);
if (node->right) helper(node->right, out + "->", res);
}
}
};
解法二：
class Solution {
public:
/**
* @param root the root of the binary tree
* @return all root-to-leaf paths
*/
vector<string> binaryTreePaths(TreeNode* root) {
if (!root) return {};
if (!root->left && !root->right) return {to_string(root->val)};
vector<string> left = binaryTreePaths(root->left);
vector<string> right = binaryTreePaths(root->right);
left.insert(left.end(), right.begin(), right.end());
for (auto &a : left) {
a = to_string(root->val) + "->" + a;
}
return left;
}
};