// Definition for a binary tree node.
    [DebuggerDisplay("val = {val}")]
    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;
        }
    }

    public class TreeNodeHelper
    {
        /// <summary>
        /// Create a TreeNode from a string with numbers and nulls, with [ delimiters
        /// </summary>
        /// <param name="treeNodeStr">The tree node string has [] delimiters. It uses , to separate
        /// values. Permitted values are numbers and the word null (case insensitive).
        /// Spaces are also permitted.</param>
        /// <returns></returns>
        public static TreeNode CreateTreeForBreadthFirstValuesString(string treeNodeStr)
        {
            List<int?> valueList = ParseTreeNodeStrIntoValueArray(treeNodeStr);
            if (valueList.Count == 0)
                return null;

            TreeNode root = CreateTreeForBreadthFirstValuesArray(valueList);
            return root;
        }

        public static TreeNode CreateTreeForBreadthFirstValuesArray(IList<int?> values)
        {
            TreeNode root = new TreeNode(values[0].Value);
            AddChildNodesForBreadthFirstValues(values, 1, new TreeNode[] { root });
            return root;
        }

        private static List<int?> ParseTreeNodeStrIntoValueArray(string treeNodeStr)
        {
            List<int?> valueArray = new();

            treeNodeStr = treeNodeStr.ToLower();
            string valueListStr = treeNodeStr.Trim(' ', '[', ']');
			
			if (valueListStr.Length == 0)
                return valueArray;

            string[] valueStrArray = valueListStr.Split(",").ToArray();
            for (int i = 0; i < valueStrArray.Length; i++)
            {
                string str = valueStrArray[i].Trim();
                if (str == "null")
                {
                    valueArray.Add(null);
                }
                else
                {
                    int number = int.Parse(str);
                    valueArray.Add(number);
                }
            }

            return valueArray;
        }

        private static int GetFirstBracketIndex(string valueStr)
        {
            int firstBracketIndex = 0;
            while (firstBracketIndex < valueStr.Length - 1) // throws an exception if [ is the last character in the string
            {
                char ch = valueStr[firstBracketIndex];

                if (ch == '[')
                    break;

                if (char.IsWhiteSpace(ch))
                    firstBracketIndex++;

                throw new InvalidOperationException("Only whitespace characters are allowed before the initial [");
            }

            if (firstBracketIndex == valueStr.Length)
                throw new InvalidOperationException("Initial [ not found.");

            return firstBracketIndex;
        }

        private static int GetLastBracketIndex(string valueStr)
        {
            int lastBracketIndex = valueStr.Length - 1;
            while (lastBracketIndex >= 0)
            {
                char ch = valueStr[lastBracketIndex];

                if (ch == ']')
                    break;

                if (char.IsWhiteSpace(ch))
                    lastBracketIndex--;

                throw new InvalidOperationException("Only whitespace characters are allowed after the final ]");
            }

            if (lastBracketIndex == 0)
                throw new InvalidOperationException("Final ] not found.");

            return lastBracketIndex;
        }

        private static void AddChildNodesForBreadthFirstValues(IList<int?> values, int currentIndex, IList<TreeNode> nodesForOneLevel)
        {
            if (currentIndex >= values.Count)
                return;

            IList<TreeNode> childNodes = new List<TreeNode>();

            int numNodes = nodesForOneLevel.Count;
            for (int i = 0; i < numNodes; i++)
            {
                TreeNode node = nodesForOneLevel[i];

                int? value = values[currentIndex++];
                if (value.HasValue)
                {
                    node.left = new TreeNode(value.Value);
                    childNodes.Add(node.left);
                }

                value = values[currentIndex++];
                if (value.HasValue)
                {
                    node.right = new TreeNode(value.Value);
                    childNodes.Add(node.right);
                }
            }

            AddChildNodesForBreadthFirstValues(values, currentIndex, childNodes);
        }
    }

    public class MyTests
    {
        Solution _underTest = new Solution();

        public void RunTests()
        {
            Test1();
            Test2();
            Test3();
        }

        public void Test1()
        {
            string treeNodeStr = "[1, 2, 3, 4, 5, null, 6, 7, null, null, null, null, 8]";
            TreeNode root = TreeNodeHelper.CreateTreeForBreadthFirstValuesString(treeNodeStr);

            int sum = _underTest.DeepestLeavesSum(root);
            Console.WriteLine($"01 Expected 15, Actual is {sum}");
        }

        public void Test2()
        {
            string treeNodeStr = "[6, 7, 8, 2, 7, 1, 3, 9, null, 1, 4, null, null, null, 5]";
            TreeNode root = TreeNodeHelper.CreateTreeForBreadthFirstValuesString(treeNodeStr);

            int sum = _underTest.DeepestLeavesSum(root);
            Console.WriteLine($"02 Expected 19, Actual is {sum}");
        }

        public void Test3()
        {
            string treeNodeStr = "[6]";
            TreeNode root = TreeNodeHelper.CreateTreeForBreadthFirstValuesString(treeNodeStr);

            int sum = _underTest.DeepestLeavesSum(root);
            Console.WriteLine($"03 Expected 6, Actual is {sum}");
        }
    }