On the Deserialization of a Binary Tree

-
Problem is here: https://leetcode.com/problems/construct-binary-tree-from-string/

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:
  1. There will only be '(', ')', '-' and '0' ~ '9' in the input string.
  2. An empty tree is represented by "" instead of "()".
It deals with the deserialization of a tree, which was addressed before more generically here. Basically my approach was:

  • 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

Popular posts from this blog

Count Binary Substrings

-
Image
Problem by Leetcode:  https://leetcode.com/problems/count-binary-substrings/description/ Give a string  s , count the number of non-empty (contiguous) substrings that have the same number of 0's and 1's, and all the 0's and all the 1's in these substrings are grouped consecutively. Substrings that occur multiple times are counted the number of times they occur. Example 1: Input: "00110011" Output: 6 Explanation: There are 6 substrings that have equal number of consecutive 1's and 0's: "0011", "01", "1100", "10", "0011", and "01". Notice that some of these substrings repeat and are counted the number of times they occur. Also, "00110011" is not a valid substring because all the 0's (and 1's) are not grouped together. Example 2: Input: "10101" Output: 4 Explanation: There are 4 substrings: "10", "01", "10", "01&
Read more

Count Vowels Permutation: Standard DP

-
Image
Standard DP problem:  https://leetcode.com/problems/count-vowels-permutation/ Given an integer  n , your task is to count how many strings of length  n  can be formed under the following rules: Each character is a lower case vowel ( 'a' ,  'e' ,  'i' ,  'o' ,  'u' ) Each vowel  'a'  may only be followed by an  'e' . Each vowel  'e'  may only be followed by an  'a'  or an  'i' . Each vowel  'i'   may not  be followed by another  'i' . Each vowel  'o'  may only be followed by an  'i'  or a  'u' . Each vowel  'u'  may only be followed by an  'a'. Since the answer may be too large, return it modulo  10^9 + 7. Example 1: Input: n = 1 Output: 5 Explanation: All possible strings are: "a", "e", "i" , "o" and "u". Example 2: Input: n = 2 Output: 10 Explanation: All possible strings are
Read more

Maximum Number of Balloons

-
Image
#431 in my solved list:  https://leetcode.com/problems/maximum-number-of-balloons/ Given a string  text , you want to use the characters of  text  to form as many instances of the word  "balloon"  as possible. You can use each character in  text   at most once . Return the maximum number of instances that can be formed.   Example 1: Input: text = "nlaebolko" Output: 1 Example 2: Input: text = "loonbalxballpoon" Output: 2 Example 3: Input: text = "leetcode" Output: 0 Constraints: 1 <= text.length <= 10^4 text  consists of lower case English letters only. Solution is as follows:  - Count the number of occurrences of the "balloon" letters in the input string  - For "l" and "o", divide the count by 2  - If the balloon string is not fully covered, return 0  - Return the min number across all occurrences Code is below, cheers, ACC. public class Solution {     public int M
Read more