Leetcode 257: Binary Tree Paths

 https://leetcode.com/problems/binary-tree-paths/description/

Notes:

This question is a typical warm-up question in the interview. So the key is to get it done clearly and quickly. (and bug-free)

Since it is a tree, so recursion is the first choice. 

And it requests to print the path, so dfs is a better choice (than bfs). 

Then ending condition (base case) is when the node is a leaf (both left and right are null).

A hidden ending condition is when the current node is null.

See the code below:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> res;
        dfs(root, "", res);
        return res;
    }
private:
    void dfs(TreeNode* r, string s, vector<string>& res) {
        if(!r) return;
        if(!r->left && !r->right) res.push_back(s + to_string(r->val));
        dfs(r->right, s + to_string(r->val) + "->", res);
        dfs(r->left, s + to_string(r->val) + "->", res);
    }
};