题目地址：https://leetcode-cn.com/problems/construct-binary-tree-from-string/
题目描述
Youneed to construct a binary tree from a string consisting of parenthesis and integers.
Thewhole 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.
Youalways 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 "()".
题目大意
判断一个多边形是不是凸多边形。
解题方法
统计字符串出现的次数
看到括号匹配，大部分做法当然是用栈来解决，其实可以直接用统计的方法完成。
即从左向右统计括号出现的次数count，如果是'('则增加1，如果是')'则减小1，如果count == 0了，说明已经完成了一个括号匹配。
这个题中的格式是root(left)(right)，最多只会出现两个完美匹配的外部括号，分别找出两个左括号的位置first和second，然后使用剪切字符串并递归生成左右孩子。
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;
}
};
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 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44
2022
DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有
本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发