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)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
// 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.
Be First to Comment