# 536. Construct Binary Tree from String 从字符串生成二叉树

@TOC

## # 题目描述

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 "()".

## # 解题方法

### # 统计字符串出现的次数

C++代码如下：

``````/**
* 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) {
if (s.empty()) return nullptr;
TreeNode* root = new TreeNode(s[0]);
int cnt = count(s.begin(), s.end(), '(');
int first = -1;
int second = -1;
int count = 0;
for (int i = 0; i < s.size(); ++i) {
if (s[i] == '(') {
count ++;
if (count == 1) {
if (first == -1)
first = i;
else
second = i;
}
} else if (s[i] == ')') {
count --;
}
}
if (first == -1) {
root->val = atoi(s.c_str());
} else if (second == -1) {
root->val = atoi(s.substr(0, first).c_str());
root->left = str2tree(s.substr(first + 1, s.size() - first));
} else {
root->val = atoi(s.substr(0, first).c_str());
root->left = str2tree(s.substr(first + 1, second - first));
root->right = str2tree(s.substr(second + 1, s.size() - second));
}
return root;
}
};
``````

## # 日期

2019 年 9 月 20 日 —— 是选择中国互联网式加班？还是外企式养生？