On the Deserialization of a Binary Tree
Problem is here: https://leetcode.com/problems/construct-binary-tree-from-string/
It deals with the deserialization of a tree, which was addressed before more generically here. Basically my approach was:
536. Construct Binary Tree from String
Medium
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"()".
- First have some simple code to pick up the initial number value to be used for the current node (watch out for the possibility of negative numbers)
- Write a routine which will parse the brackets into left and right. That's the one that you'll have to be very careful and detailed with the indexes calculations, but once you get past that, it is a breeze
Code is below, cheers, ACC.
public class Solution
{
public TreeNode Str2tree(string s)
{
if (String.IsNullOrEmpty(s)) return null;
int number = 0;
int index = 0;
int sign = 1;
while (index < s.Length &&
(s[index] == '-' || (s[index] >= '0' && s[index] <= '9')))
{
if (s[index] == '-') sign = -1;
else
{
number = 10 * number + Int32.Parse(s[index].ToString());
}
index++;
}
number *= sign;
TreeNode node = new TreeNode(number);
string left = "";
string right = "";
ParseBrackets(s.Substring(index), ref left, ref right);
node.left = Str2tree(left);
node.right = Str2tree(right);
return node;
}
private void ParseBrackets(string s,
ref string left,
ref string right)
{
if (String.IsNullOrEmpty(s))
{
left = right = "";
return;
}
//Left
int countBrackets = 0;
int begin = 0;
int end = 0;
for (int i = 0; i < s.Length; i++)
{
if (s[i] == '(')
{
if (countBrackets == 0)
{
begin = i;
}
countBrackets++;
}
if (s[i] == ')') countBrackets--;
if (countBrackets == 0)
{
end = i;
break;
}
}
if (end > begin)
{
left = s.Substring(begin + 1, end - begin - 1);
}
else
{
left = "";
}
countBrackets = 0;
int init = end + 1;
begin = 0;
end = 0;
for (int i = init; i < s.Length; i++)
{
if (s[i] == '(')
{
if (countBrackets == 0)
{
begin = i;
}
countBrackets++;
}
if (s[i] == ')') countBrackets--;
if (countBrackets == 0)
{
end = i;
break;
}
}
if (end > begin)
{
right = s.Substring(begin + 1, end - begin - 1);
}
else
{
right = "";
}
}
}
Comments
Post a Comment