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 1:
Input: s = "4(2(3)(1))(6(5))" Output: [4,2,6,3,1,5]
Example 2:
Input: s = "4(2(3)(1))(6(5)(7))" Output: [4,2,6,3,1,5,7]
Example 3:
Input: s = "-4(2(3)(1))(6(5)(7))" Output: [-4,2,6,3,1,5,7]
Constraints:
0 <= s.length <= 3 * 104sconsists of digits,'(',')', and'-'only.
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* str2tree(string s) {
int i = 0;
return helper(s, i);
}
TreeNode* helper(string s, int& idx) {
if (idx == s.size()) {
return NULL;
}
int st = idx;
if (s[idx] == '-') {
idx++;
}
while (idx < s.size() && (isdigit(s[idx]))) {
idx++;
}
TreeNode *node = new TreeNode(stoi(s.substr(st, idx - st)));
if (idx == s.size()) {
return node;
}
if (s[idx] == '(') {
idx++;
node -> left = helper(s, idx);
idx++;
}
if (s[idx] == '(') {
idx++;
node -> right = helper(s, idx);
idx++;
}
return node;
}
};
===============
TreeNode* str2tree(string s)
{
if(s.empty()) return NULL;
stack<TreeNode*> st;
int j=0;
for(int i=0; i<s.size(); i++)
{
j = i;
if(s[i]==')') st.pop();
if( (i<s.size() && s[i]>='0' && s[i]<='9') || s[i]=='-' )
{
while(s[i+1]>='0' && s[i+1]<='9') i++;
TreeNode* cur = new TreeNode(stoi(s.substr(j, i-j+1)));
if(!st.empty())
{
auto t = st.top();
if(!t->left) t->left = cur;
else t->right = cur;
}
st.push(cur);
}
}
return st.top();
}
No comments:
Post a Comment