536 Construct binary tree from string - Sept. 18, 2023

536ConstructBinaryTreeFromString.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _536_constructBinaryTreeFromString
{
    class Program
    {
        public class TreeNode {
          public int val;
          public TreeNode left;
          public TreeNode right;
          public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
              this.val = val;
              this.left = left;
              this.right = right;
          }
        }

        static void Main(string[] args)
        {
            var test = new Program(); 

            //var result1 = test.Str2tree("2(3)(1)");
            var result5 = test.Str2tree("4(2(3)(1))(6(5))");
        }

        /// <summary>
        /// 536 Construct binary tree from string 
        /// </summary>
        /// <param name="s"></param>
        /// <returns></returns>
        public TreeNode Str2tree(string s)
        {
            return str2treeInternal(s, 0).Item1; 
        }

        /// <summary>
        /// Parse an integer starting from given position - index 
        /// </summary>
        /// <param name="s"></param>
        /// <param name="index"></param>
        /// <returns></returns>
        private Tuple<int, int> getNumber(String s, int index)
        {
            var isNegative = false;

            // A negative number
            if (s[index] == '-')
            {
                isNegative = true;
                index++;
            }

            int number = 0;
            // Use Char.IsDigit to save time
            while (index < s.Length && Char.IsDigit(s[index]))
            {
                number = number * 10 + (s[index] - '0');
                index++;
            }

            return new Tuple<int, int>(isNegative ? -number : number, index);
        }

        /// <summary>
        /// Work on recursive function - basics of recursive function design 
        /// </summary>
        /// <param name="s"></param>
        /// <param name="index"></param>
        /// <returns></returns>
        private Tuple<TreeNode, int> str2treeInternal(string s, int index)
        {
            if (index == s.Length)
            {
                return new Tuple<TreeNode, int>(null, index);
            }

            // Start of the tree will always contain a number representing
            // the root of the tree. So we calculate that first.
            var tuple = getNumber(s, index);

            int value = tuple.Item1;
            index = tuple.Item2;

            var node = new TreeNode(value);                      

            // Next, if there is any data left, we check for the first subtree
            // which according to the problem statement will always be the left child.
            if (index < s.Length && s[index] == '(')
            {
                var data = this.str2treeInternal(s, index + 1);

                node.left = data.Item1;
                index = data.Item2;
            }

            // Indicates a right child
            if (node.left != null && index < s.Length && s[index] == '(')
            {
                var data = this.str2treeInternal(s, index + 1);

                node.right = data.Item1;
                index = data.Item2;
            }

            // 
            return new Tuple<TreeNode, int>(node, index < s.Length && s[index] == ')' ? index + 1 : index);
        }
    }
}