Leetcode 536. Construct Binary Tree from String

You need to construct a binary tree from a string consisting of parenthesis and integers.

The whole input represents a binary tree. It contains an integer followed by zero, one or two pairs of parenthesis. The integer represents the root’s value and a pair of parenthesis contains a child binary tree with the same structure.

You always start to construct the left child node of the parent first if it exists.

Example:
Input: "4(2(3)(1))(6(5))"
Output: return the tree root node representing the following tree:

       4
     /   \
    2     6
   / \   / 
  3   1 5

 

Note:
There will only be ‘(‘, ‘)’, ‘-‘ and ‘0’ ~ ‘9’ in the input string.
An empty tree is represented by “” instead of “()”.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* str2tree(string s) {
        int i = 0;
        return dfs(s, i);
    }

    int get_next_num(string &s, int &i) {
        int start = i;
        while (i != (int)s.size() && s[i] != '(' && s[i] != ')')
            i++;

        return stoi(s.substr(start, i - start));
    }
/*
 0123456789
 4(2(3)(1))(6(5))

 4(2)(3)

*/
    TreeNode *dfs(string &s, int &i) {
        //base case
        int size = s.size();
        if (i >= size || s[i] == ')')
            return NULL;

        if (s[i] == '(')
            i++;

        int num = get_next_num(s, i);
        TreeNode *root = new TreeNode(num);

        TreeNode *left = dfs(s, i);
        TreeNode *right = dfs(s, i);

        root->left = left;
        root->right = right;

        if (s[i] == ')')
            i++;

        return root;
    }
};

 

 

Leave a Reply