花花酱 LeetCode 257. Binary Tree Paths

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

Solution: Recursion

Time complexity: O(n)
Space complexity: O(n) / output can be O(n^2)

// Author: Huahua

class Solution {

public:

vector<string> binaryTreePaths(TreeNode* root) {

vector<string> ans;

string s;

function<void(TreeNode*, int)> preorder = [&](TreeNode* node, int l) {

if (!node) return;

s += (l > 0 ? "->" : "") + to_string(node->val);

if (!node->left && !node->right)

ans.push_back(s);

preorder(node->left, s.size());

preorder(node->right, s.size());

while (s.size() != l) s.pop_back();

};

preorder(root, 0);

return ans;

}

};

请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.

Buy anything from Amazon to support our website
您可以通过在亚马逊上购物（任意商品）来支持我们

Paypal

Venmo
huahualeetcode

微信打赏