2017年408大题第一题
/**
* Definition for a binary tree node.
* struct TreeNode {
* string val;
* TreeNode *left;
* TreeNode *right;
* };
*/
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);
}
};
注意:这个算法实现看似是线性的,但在实际C++返回string过程中需要复制一遍,所以总来实际时间复杂度O(n^2)
优化写法:把所有返回string写法改成全局变量赋值法
/**
* 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) 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;
}
};
标准答案:
(1) 算法的基本设计思想
表达式树的中序序列加上必要的括号即为等价的中缀表达式。可以基于二叉树的中序遍历
策略得到所需的表达式。(3分)
表达式树中分支结点所对应的子表达式的计算次序,由该分支结点所处的位置决定。为得
到正确的中缀表达式,需要在生成遍历序列的同时,在适当位置增加必要的括号。显然,表达
式的最外层(对应根结点)及操作数(对应叶结点)不需要添加括号。(2分)
(2)算法实现(10分)
void BtreeToE(BTree * root)
{
BtreeToExp(root,1); //根的高度为1
void BtreeToExp(BTree * root, int deep)
{
if( root = = NULL) return;
else if(root->left = = NULL && root->right = = NULL)
//若为叶结点
printf(“%s”,root->data); //输出操作数
else
{
if(deep>1) printf(“(”);//若有子表达式则加1层括号
BtreeToExp(root->left,deep+1);
printf(“%s”,root->data); //输出操作符
BtreeToExp(root->right,deep+1);
if(deep>1) printf(“)”);//若有子表达式则加1层括号
}
}