Construct_String_from_Binary_Tree

/**
 * 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:
        std::string tree2str(TreeNode* root) {
            // Step 1: Base case - if the root is null, return an empty string
            if (root == nullptr) {
                return "";
            }
    
            // Step 2: Start with the value of the current node as the result string
            std::string result = std::to_string(root->val);
    
            // Step 3: Recursively process the left and right subtrees
            std::string leftSubtree = tree2str(root->left);
            std::string rightSubtree = tree2str(root->right);
    
            // Step 4: Check conditions to determine the final result
            if (leftSubtree.empty() && rightSubtree.empty()) {
                // Both left and right subtrees are empty, return the current result
                return result;
            }
            if (leftSubtree.empty()) {
                // Left subtree is empty, include empty parentheses for it and the right subtree
                return result + "()" + "(" + rightSubtree + ")";
            }
            if (rightSubtree.empty()) {
                // Right subtree is empty, include the left subtree
                return result + "(" + leftSubtree + ")";
            }
    
            // Both left and right subtrees are non-empty, include both in the result
            return result + "(" + leftSubtree + ")" + "(" + rightSubtree + ")";
        }
    };

   /*  Input: root = [1,2,3,4]
Output: "1(2(4))(3)"
Explanation: Originally, it needs to be "1(2(4)())(3()())", but you need to omit all the unnecessary empty parenthesis pairs. And it will be "1(2(4))(3)"  */