本文共 2034 字，大约阅读时间需要 6 分钟。

You need to construct a string consists of parenthesis and integers from a binary tree with the preorder traversing way.

The null node needs to be represented by empty parenthesis pair "()" . And you need to omit all the empty parenthesis pairs that don’t affect the one-to-one mapping relationship between the string and the original binary tree.

Example 1:

Input: Binary tree: [1,2,3,4]       1     /   \    2     3   /      4     Output: "1(2(4))(3)"Explanation: Originallay it needs to be "1(2(4)())(3()())", but you need to omit all the unnecessary empty parenthesis pairs. And it will be "1(2(4))(3)".

Example 2:

Input: Binary tree: [1,2,3,null,4]       1     /   \    2     3     \        4 Output: "1(2()(4))(3)"Explanation: Almost the same as the first example, except we can't omit the first parenthesis pair to break the one-to-one mapping relationship between the input and the output.

题意：从一棵二叉树中，使用先序遍历方式，构建一个由括号和整数组成的字符串。注意：空的结点需要用 "()" 代替，还需要省略所有的不影响字符串和原始二叉树之间一一对应关系的 "()" 。

一个已知的例子是LeetCode中给出的描述树结点的数组，使用层序遍历方式，从树中构建一个数组，省略所有不影响数组和原始树之间一一对应关系的 null 值。如 [1,2,3,null,4] ：

如果不使用层序序列，而是先序或后序序列的话，就需要两个数组，加上一个中序数组。因为单一数组无法表达树的递归关系。

思路 递归遍历

这里我们注意到，使用一个 "()" 分别包括左子树、右子树，令仅用一个线性表表达树关系成为可能。从示例中注意到：

• 如果一个结点是叶子结点，那么它的左右空子树无需表达，即省略对应的 "()" ；
• 如果一个结点有一个孩子，那么视情况而定：
  • 只有左孩子，那么空的右子树对应的 "()" 可以省略；
  • 只有右孩子，为了区分左右子树，空的左子树对应的 "()" 不可以省略；
• 如果一个结点有两个孩子，则都需要表达。

对应的代码很简单：

class Solution {
   public:    string ans;    void preorder(TreeNode* root) {
           ans.append(to_string(root->val));        if (root->left) {
    //左子树非空            ans.push_back('(');            preorder(root->left);            ans.push_back(')');        } else if (root->right) ans.append("()"); //左子树为空但是右子树非空        if (root->right) {
    //右子树非空            ans.push_back('(');            preorder(root->right);            ans.push_back(')');        }      }    string tree2str(TreeNode* t) {
           if (t == nullptr) return "";        preorder(t);        return ans;    }};

效率如下：

执行用时：24 ms, 在所有 C++ 提交中击败了94.61% 的用户内存消耗：23.3 MB, 在所有 C++ 提交中击败了71.13% 的用户

转载地址：https://memcpy0.blog.csdn.net/article/details/108940513 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！