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

示例输入:

    +
   / \
  12  *
     / \
    6   4

示例输出:

12 + (6 * 4)

注意:

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

数据范围:

给定二叉树的非空结点数量保证不超过 1000。 给定二叉树保证能够转化为合法的中缀表达式。

代码实现

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     string val;
 *     TreeNode *left;
 *     TreeNode *right;
 * };
 */
class Solution {
public:
    string s = "";
    bool isDigit(TreeNode* root) {
        return !(root->val == "+" || root->val == "-" || root->val == "*" || root->val == "/");
    }
    void dfs(TreeNode* root) {
        if (!root) return ;
        if (root->left && !isDigit(root->left)) s += '(';
        if (root->left) dfs(root->left);
        if (root->left && !isDigit(root->left)) s += ')';
        s += root->val;
        if (root->right && !isDigit(root->right)) s += '(';
        if (root->right) dfs(root->right);
        if (root->right && !isDigit(root->right)) s += ')';
    }
    string expressionTree(TreeNode* root) {
        dfs(root);
        return s;
    }
};
分类: Tree

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status