AcWing.3765 表达式树

请设计一个算法，将给定的表达式树(二叉树)转换为等价的中缀表达式(通过括号反映操作符的计算次序)并输出。

例如，当下列两棵表达式树作为算法的输入时：

输出的等价中缀表达式分别为 (a+b)*(c*(-d)) 和 (a*b)+(-(c-d))。

注意：

• 树中至少包含一个运算符。
• 当运算符是负号时，左儿子为空，右儿子为需要取反的表达式。
• 树中所有叶节点的值均为非负整数。

样例：

输入：二叉树[+, 12, *, null, null, 6, 4, null, null, null, null]如下图所示：
    +
   / \
  12  *
     / \
    6   4

输出：12+(6*4)

数据范围

给定二叉树的非空结点数量保证不超过 $1000$。

给定二叉树保证能够转化为合法的中缀表达式。

时间复杂度

为$O(n^2)$
因为C++中字符串return并不是直接返回，而是先复制一遍再返回。
为了优化，可以不适用return进行返回，而是定义一个全局变量ans来记录最终的答案。

Code

未优化的，时间复杂度：$O(n^2)$

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     string val；
 *     TreeNode *left;
 *     TreeNode *right;
 * };
 */
class Solution {
public:
    string dfs(TreeNode* root) {
        if(root == NULL) return "";  // 如果结点为空返回空
        
        // 如果是叶节点，就返回当前的值
        if(root->left == NULL && root->right == NULL) 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)$

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     string val；
 *     TreeNode *left;
 *     TreeNode *right;
 * };
 */
class Solution {
public:
    string ans;  // 定义全局变量

    void dfs(TreeNode* root) {
        if(root == NULL) return;
        
        // 如果是叶节点，就让ans加上当前的值
        if(root->left == NULL && root->right == NULL)
        {
            ans += root->val;
            return;
        }
        
        // 如果不是叶节点，就让ans递归加上，记得加上()
        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;
    }
};