[数据结构与算法]二叉树转字符串及字符串转二叉树

目录

一.二叉树转字符串

二.字符串转二叉树

---

一.二叉树转字符串

1.对应lintcode链接：

1137 · 从二叉树构建字符串 - LintCode

2.题目描述：

3.解题思路：

本题就是简单的前序遍历：具体步骤如下

1.如果当前节点有两个孩子，那我们在递归时，需要在两个孩子的结果外都加上一层括号；
2.如果当前节点没有孩子，那我们不需要在节点后面加上任何括号；
3.如果当前节点只有左孩子，那我们在递归时，只需要在左孩子的结果外加上一层括号，而不需要给右孩子加上任何括号；
4.如果当前节点只有右孩子，那我们在递归时，需要先加上一层空的括号 ‘()’ 表示左孩子为空，再对右孩子进行递归，并在结果外加上一层括号。

4.对应代码：

 string tree2str(TreeNode *root) {
        // write your code here
        if(root==nullptr){
            return "";
        }
        string ans;
        ans+=to_string(root->val);
        if(root->left||root->right){//有左子树时需要加括号没左子树但是有右子树也要加括号
            ans+="(";
            ans+=tree2str(root->left);
            ans+=")";
        }
        if(root->right){
             ans+="(";
            ans+=tree2str(root->right);
            ans+=")";
        }
        return ans;
    }
};

我们发现这里多次调用的时候会发生很多次拷贝我们可以使用子函数进行优化：

class Solution {
public:
    /**
     * @param t: the root of tree
     * @return: return a string
     */
     string ans;
    string tree2str(TreeNode *t) {
        // write your code here
        _tree2str(t);
        return ans;
    }
    void _tree2str(TreeNode*root)
    {
        if(root==nullptr){
            return;
        }
        ans+=to_string(root->val);
        if(root->left||root->right){
            ans+="(";
            _tree2str(root->left);
            ans+=")";
        }
        if(root->right){
            ans+="(";
            _tree2str(root->right);
            ans+=")";
        }
    }
};

二.字符串转二叉树

1.对应lintcode链接

880 · 字符串构造二叉树 - LintCode

2.题目描述：

3.解题思路：

1.首先，对于上例字符串4(2(3)(1))(6(5)),当遍历到字符串中非括号字符时, 这个数字就用来构造根节点。
2.找到其后第一个(出现的位置，这里是1,并用一个括号统计变量count记录需要右括号的数量，每当遇到一个左括号，count++，遇到一个右括号count--，那么当count记录值为0时，我们就找到了一个子树。上例中，count==0时找到的子树为(2(3)(1))，那么它就是4的左子树构成部分.
3.对于右子树的构建，我们之前记录了左子树的开始位置，那么当count再次为0时，此时对应的起点与第一次遇到(的位置不同，那么这其后的部分(6(5))就作为右子树.
构建左右子树时，将两端的括号消去。
4.递归完成构建。

4.对应代码：

class Solution {
public:
    /**
     * @param s: a string
     * @return: a root of this tree
     */
   TreeNode* str2tree(string s) {
        if(s.empty()){
            return nullptr;
        }
      int pos=s.find('(');

      if(pos==-1)
      {
          return new TreeNode(stoi(s));
      }

    int start=pos;
    int cnt=0;
    //遇到左括号++，遇到右括号--
    TreeNode*root=new TreeNode(stoi(s.substr(0,pos)));

    for(int i=pos;i<s.size();i++)
    {
        if(s[i]=='(')
        {
            cnt++;
        }
        else if(s[i]==')'){
            cnt--;
        }
       if(cnt==0&&start==pos){//说明是左子树
       //i-start+1.
          root->left=str2tree(s.substr(start+1,i-1-start));
          start=i+1;
       }
       else if(cnt==0&&start!=pos){
      root->right=str2tree(s.substr(start+1,i-1-start));
       }
        
    }
      return root;
     
    }
    
};