Binary tree to string and string to binary tree

Catalog

One . Binary tree to string

Two . String to binary tree

---

One . Binary tree to string

1. Corresponding lintcode link ：

1137 · Build a string from a binary tree - LintCode

2. Title Description ：

3. Their thinking ：

This problem is a simple preorder traversal ： The specific steps are as follows

1. If the current node has two children , So when we recurse , You need to put a layer of parentheses outside the results of both children ;
2. If the current node has no children , Then we don't need to put any parentheses after the node ;
3. If the current node has only left children , So when we recurse , Just add a layer of parentheses to the left child's result , There is no need to add any parentheses to the right child ;
4. If the current node has only right children , So when we recurse , You need to add a layer of empty parentheses first ‘()’ Indicates that the left child is empty , Then recurse to the right child , And add a layer of parentheses to the result .

4. The corresponding code ：

 string tree2str(TreeNode *root) {
        // write your code here
        if(root==nullptr){
            return "";
        }
        string ans;
        ans+=to_string(root->val);
        if(root->left||root->right){// If there is a left subtree, you need to add brackets. If there is no left subtree, but if there is a right subtree, you also need to add brackets 
            ans+="(";
            ans+=tree2str(root->left);
            ans+=")";
        }
        if(root->right){
             ans+="(";
            ans+=tree2str(root->right);
            ans+=")";
        }
        return ans;
    }
};

We found that there will be many copies when multiple calls are made here. We can use sub functions to optimize ：

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+=")";
        }
    }
};

Two . String to binary tree

1. Corresponding lintcode link

880 · String construct binary tree - LintCode

2. Title Description ：

3. Their thinking ：

1. First , For the above example string 4(2(3)(1))(6(5)), When traversing to non bracketed characters in a string , This number is used to construct the root node .
2. Find the next one ( Position of appearance , Here is 1, And use a bracket to count the variables count Record the number of closing parentheses required , Whenever an open parenthesis is encountered ,count++, Encountered a closing parenthesis count--, So when count The recorded value is 0 when , We found a subtree . In the above example ,count==0 The subtree found in is (2(3)(1)), So it's going to be 4 The left subtree of .
3. For the construction of right subtree , We recorded the starting position of the left subtree , So when count Again for 0 when , At this point, the corresponding starting point is the first encounter ( The location is different , So the following part (6(5)) As a right subtree .
When building left and right subtrees , Remove the parentheses at both ends .
4. Recursively complete the build .

4. The corresponding code ：

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;
    // Left parenthesis encountered ++, Right parenthesis encountered --
    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){// The description is a left subtree 
       //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;
     
    }
    
};