欢迎访问==> 【考研OR保研】机试题
题目描述
请设计一个算法,将给定的表达式树(二叉树)转换为等价的中缀表达式(通过括号反映操作符的计算次序)并输出。
例如,当下列两棵表达式树作为算法的输入时:
输出的等价中缀表达式分别为 (a+b)*(c*(-d))
和 (a*b)+(-(c-d))
。
注意:
- 树中至少包含一个运算符。
- 当运算符是负号时,左儿子为空,右儿子为需要取反的表达式。
- 树中所有叶节点的值均为非负整数。
样例:
输入:二叉树[+, 12, *, null, null, 6, 4, null, null, null, null]如下图所示:
+
/ \
12 *
/ \
6 4
输出:12+(6*4)
数据范围
给定二叉树的非空结点数量保证不超过 $1000$。
给定二叉树保证能够转化为合法的中缀表达式。
C++ 代码
相当于二叉树的中序遍历
在中序遍历的过程中注意加上括号即可
/**
* Definition for a binary tree node.
* struct TreeNode {
* string val;
* TreeNode *left;
* TreeNode *right;
* };
*/
class Solution {
public:
string res;
void dfs(TreeNode* root)
{
if(!root) return;
if(!root->left && !root->right) res += root->val;
else res += "(", dfs(root->left), res += root->val, dfs(root->right), res += ")";
}
string expressionTree(TreeNode* root) {
dfs(root->left), res += root->val, dfs(root->right);
return res;
}
};