/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     string val；
 *     TreeNode *left;
 *     TreeNode *right;
 * }; 
 */


//O(n^2)  return时string是复制了一遍 
class Solution {
public:

    string dfs(TreeNode* root){
        if(!root)   return "";
        if(!root->left && !root->right) return  root->val;
        return '(' +dfs(root->left) + root->val  + dfs(root->right) + ')';
    }


    string expressionTree(TreeNode* root) {
        return dfs(root->left) + root->val + dfs(root->right);
    }
};


//O(n)
class Solution {
public:
    string ans;

    void dfs(TreeNode* root){
        if(!root)   return;
        if(!root->left && !root->right) ans += root->val;
        else{
            ans += '(';
            dfs(root->left);
            ans += root->val;
            dfs(root->right);
            ans += ')';
        }
    }


    string expressionTree(TreeNode* root) {
        dfs(root->left);
        ans += root->val;
        dfs(root->right);

        return ans;
    }
};