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:

1. There will only be '(', ')', '-' and '0' ~ '9' in the input string.
2. An empty tree is represented by "" instead of "()".

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

/** * 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 { int pos = 0; public: TreeNode* str2tree(string s) { int n = s.size(); if(n==pos) return NULL; //compose the number int start = pos; while(pos<n && (s[pos]=='-'||isdigit(s[pos]))){pos++;} string v = s.substr(start, pos-start); TreeNode* node = new TreeNode(stoi(v)); //dfs if(pos<n && s[pos]=='('){ pos++; node->left = str2tree(s);} if(pos<n && s[pos]=='('){ pos++; node->right = str2tree(s);} if(pos<n && s[pos]==')') pos++; return node; } };