Binary Tree Paths

Problem:

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

For example, given the following binary tree:

   1
 /   \
2     3
 \
  5

All root-to-leaf paths are:

["1->2->5", "1->3"]

Solution:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> ans; string path;
        if (root == NULL) {
            return ans;
        } else {
            btPath(ans, path, root);
        }
        return ans;
    }
    void btPath(vector<string>& ans, string path, TreeNode* root) {
       path += (path != "" ? "->" + to_string(root -> val): to_string(root -> val));
       if (root -> left == NULL && root -> right == NULL) {
            ans.push_back(path);
        }
        if (root -> left != NULL) {
            btPath(ans, path, root->left);
        }
        if (root -> right != NULL) {
            btPath(ans, path, root->right);
        }
    }
};

===== Another ========
    void btpath(TreeNode *root, string str, vector<string>& ans) {
        if (str == "") {
            str += to_string(root -> val);
        } else {
            str += "->" + to_string(root->val);
        }
     
        if (root -> left == NULL && root -> right == NULL) {
            ans.push_back(str);
        }
        if (root -> left != NULL) {
            btpath(root->left, str, ans);
        }
        if (root -> right != NULL) {
            btpath(root->right, str, ans);
        }
    }
 
    vector<string> binaryTreePaths(TreeNode* root) {
        string str;
        vector<string> ans;
        if (root == NULL) {
            return ans;
        }
        btpath(root, str, ans);
        return ans;
    }

======= Additional complications :) =====

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void helper(TreeNode* root, vector<string>& ans, string s) {
        if (root == NULL) {
            return;
        } else if (root -> left == NULL && root -> right == NULL) {
            if (!s.empty()) {
                ans.push_back(s + "->" + to_string(root->val));
            } else {
                ans.push_back(to_string(root->val));
            }
        } else {
            if (!s.empty()) {
                s = s + "->" + to_string(root->val);
                helper(root -> left, ans, s);
                helper(root -> right, ans, s);
            } else {
                helper(root -> left, ans, to_string(root->val));
                helper(root -> right, ans, to_string(root->val));
            }
        }
    }
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> ans;
        string s;
        helper(root, ans, s);
        return ans;
    }
};

=========== 2020 ========

/**

 * 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) {

        // BFS.

        vector<string> ans;

        queue<pair<TreeNode*, string>> q;

        if (root == NULL) {

            return ans;

        }

        q.push(make_pair(root, to_string(root -> val)));

        while (!q.empty()) {

            pair<TreeNode*, string> node = q.front(); q.pop();

            if (node.first -> left != NULL) {

                q.push(make_pair(node.first -> left, node.second + "->" + to_string(node.first->left -> val)));

            }

            if (node.first -> right != NULL) {

                q.push(make_pair(node.first -> right, node.second + "->" + to_string(node.first->right -> val)));

            }

            if (node.first -> left == NULL && node.first -> right == NULL) {

                ans.push_back(node.second);

            }

        }

        return ans;

        

        /*

        // DFS

        void btpath(TreeNode *root, string str, vector<string>& ans) {

            if (str == "") {

                str += to_string(root -> val);

            } else {

                str += "->" + to_string(root->val);

            }

            if (root -> left == NULL && root -> right == NULL) {

                ans.push_back(str);

            }

            if (root -> left != NULL) {

                btpath(root->left, str, ans);

            }

            if (root -> right != NULL) {

                btpath(root->right, str, ans);

            }

        }

        vector<string> binaryTreePaths(TreeNode* root) {

            string str;

            vector<string> ans;

            if (root == NULL) {

                return ans;

            }

            btpath(root, str, ans);

            return ans;

        }

        */

    }

};