瑞文考研算法每日一题—2023.06.07 表达式树

Problem: 3765. 表达式树
此题为2017年计算机学科专业基础408真题第41题。

方法一：递归

思路

  不考虑表达式之间的括号关系，可以发现中缀表达式与二叉树的中序遍历是等价的。

  考虑括号关系，由于二叉树的中序遍历可以通过递归实现，即$左子树\to 根\to 右子树$。除了根节点外，当子树只有一个结点时表示值，直接将值加入表达式中，否则每一层子树的外层需要加上()，此时结点的值表示运算符号。

  递归边界条件：结点为空。

Code

/*** Definition for a binary tree node.* struct TreeNode {*     string val；*     TreeNode *left;*     TreeNode *right;* };*/
class Solution {
public:string expressionTree(TreeNode* root) {string res;function<void(TreeNode*)> dfs = [&](TreeNode* node){if(node == nullptr) return;if(node->left == nullptr && node->right == nullptr) res += node->val;else{res += '(';dfs(node->left);res += node->val;dfs(node->right);res += ')';}};if(root == nullptr) return res;dfs(root->left);res += root->val;dfs(root->right);return res;}
};

复杂度

• 时间复杂度: $O(n)$

• 空间复杂度: $O(n)$