C# | Construct binary tree from string | Using stack | Ask questions

536ConstructBinaryTreeFromString.cs

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

namespace _536_quick_learner___stack
{
    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 result = test.Str2tree("2(3)(4)");
            var result2 = test.Str2tree("4(2(3)(1))(6(5))"); 

           // The following test case - exception 
           // var result3 = test.Str2tree("()");
        }

        /// <summary>
        /// Oct. 16, 2023
        /// Using stack, a solution can be written in less than 30 minutes
        /// </summary>
        /// <param name="s"></param>
        /// <returns></returns>
        public TreeNode Str2tree(string s)
        {
            var stack = new LinkedList<TreeNode>();

            TreeNode parentNode = null;
            TreeNode curNode = null;

            int sign = 1;
            int index = 0;

            // Desing questions:
            // 1. Only push TreeNode into stack
            // 2. '(' and ')' count - if matching or not - ignore
            // 3. At most two nodes into stack, one is parent node, one is child node - This is not true
            // 4. Counter example: 4(2(3)), three TreeNode will be stored in the stack, 
            // 4. When child node is popped
            // 5. How to determine if child node is left or right child
            // 6. Start to think any of the above 5 questions, it will lead success
            // 7. Also think about those questions, it is also mature enough already to choose optimal solution
            //    using stack to get time complexity O(N). 
            // 8. Think about space complexity, O(height), height is the height of tree. 
            while (index < s.Length)
            {
                var current = s[index];

                if(current == ')')
                {
                    curNode = stack.Last.Value;
                    stack.RemoveLast();

                    // keep parent node in the stack
                    parentNode = stack.Last.Value;

                    // Think a few minutes using 2(3) as an example
                    // Think using example 2(3)(4) as an example 
                    // There are two cases to discuss 
                    if (parentNode.left != null)
                    {
                        parentNode.right = curNode;
                    }
                    else
                    {
                        parentNode.left = curNode;
                    }

                    index++; 
                }
                else if (current == '-')
                {
                    sign = -1;
                    index++;
                }
                else if (current == '(')
                {
                    index++;
                }
                else
                {
                    int num = 0;
                    while (index < s.Length && s[index] >= '0' && s[index] <= '9')
                    {
                        num = num * 10 + (s[index] - '0');
                        index++; 
                    }

                    num *= sign;
                    sign = 1;
                    stack.AddLast(new TreeNode(num)); 
                }
            }

            if (stack.Any())
            {
                return stack.Last.Value; 
            }

            // ? 
            return parentNode; 
        }
    }
}