Question

Given a binary tree, return all root-to-leaf paths.

Note: A leaf is a node with no children.

Example:

Difficulty:Easy

Category:Tree, DFS

Solution

Solution 1: DFS

Time complexity: O(n) Space Complexity: O(n)

Runtime: 8 ms, faster than 100.00% of C++ online submissions for Binary Tree Paths. Memory Usage: 13 MB, less than 30.23% of C++ online submissions for Binary Tree Paths.

class Solution {
 public:
  vector<string> binaryTreePaths(TreeNode* root) {
    vector<string> ans;
    string cur;
    binaryTreePaths(root, cur, ans);
    return ans;
  }

 private:
  void binaryTreePaths(TreeNode* root, string cur, vector<string>& ans) {
    if (!root) return;
    cur += to_string(root->val);
    if (!root->left && !root->right) {
      ans.push_back(cur);
    }
    cur += "->";
    binaryTreePaths(root->left, cur, ans);
    binaryTreePaths(root->right, cur, ans);
  }
};