Leetcode 297 - Serialize and deserialize binary tree - make the code more readable, run through the test case and then understand the code, also ensure code works.

Leetcode297SerializeDeserialize3_TestCase.cs

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

namespace _297SerializeDeserializeTree_Stack
{
    public class TreeNode
    {
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(int x) { val = x; }
    }

    class Program
    {
        static void Main(string[] args)
        {
            TreeNode node1 = new TreeNode(9);
            node1.left = new TreeNode(5);
            node1.right = new TreeNode(8);
            node1.left.left = new TreeNode(1);
            node1.left.right = new TreeNode(4);
            node1.left.right.left = new TreeNode(2);
            node1.left.right.right = new TreeNode(3);

            node1.right.right = new TreeNode(7);
            node1.right.right.left = new TreeNode(6);

            string result = serialize(node1);

            TreeNode root = deserialize(result); 

        }

        /*
         * May 23, 2016
         * Preorder traversal - Use test case to help understand the code quickly.  
         * 
         * ideas to implement the solution:
         * 1. First, use an array to store a tree node;
           array[0] = value;
           array[1] = li,    // left child index, if null, -1
           array[2] = ri,    // right child index, if null, -1
         * 
         * 2. nodes will be added to an arrayList of arrays; then, convert the arraylist to a string.
         * 
         * Very good practice, get familiar with preorder traversal, and how to use it to solve problems. 
         * 
         */
        public static string serialize(TreeNode root)
        {            
            string emptyString = "";
            if (root == null) return emptyString;

            List<int[]> nodes = new List<int[]>();

            Stack<TreeNode> stack      = new Stack<TreeNode>();
            Stack<Int32> positionStack = new Stack<Int32>();

            TreeNode runner = root;
            int index = 0;
            while (true)
            {   
                // preorder traversal to construct the arraylist  
                while (runner != null)
                {
                    if (stack.Count > 0)
                    {   
                        // get the parent, and set the left and right of the parent.
                        int pi = positionStack.Peek();   // ci is the current index

                        if (runner == stack.Peek().left)
                        {   
                            // cur is left child of the parent
                            nodes[pi][1] = index;
                        }
                        else
                        {   
                            // cur is the right child of the parent
                            nodes[pi][2] = index;
                        }
                    }

                    nodes.Add(new int[] { runner.val, -1, -1 });
                    
                    stack.Push(runner);
                    positionStack.Push(index);

                    runner = runner.left;
                    ++index;
                }

                while (stack.Count > 0 && (stack.Peek().right == null || stack.Peek().right == runner))
                {
                    runner = stack.Pop();
                    positionStack.Pop();
                }

                if (stack.Count == 0 ) 
                    break;
                else 
                    runner = stack.Peek().right;
            }

            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < nodes.Count; ++i)
            {
                for (int j = 0; j < 3; ++j)
                {
                    sb.Append(nodes[i][j]);
                    sb.Append(' ');
                }
            }

            return sb.ToString();
        }

        // Decodes your encoded data to tree.
        public static TreeNode deserialize(string data)
        {
            // convert the string into an arrayList; then, reconstruct the tree using the arraylist.
            if (data.Length == 0) 
                return null;

            List<Int32> nodes = new List<Int32>();

            int index = 0;
            while (index < data.Length)
            {
                int start = index;

                while (data[index] != ' ') 
                    ++index;

                int end = index;

                nodes.Add(Int32.Parse(data.Substring(start, end-start+1)));
                ++index;
            }

            List<int[]> list = new List<int[]>();

            for (int i = 0; i < nodes.Count / 3; ++i)
            {
                int[] node = new int[3];

                for (int j = 0; j < 3; ++j)
                {
                    node[j] = nodes[i * 3 + j];
                }

                list.Add(node);
            }

            // reconstruct the tree using the list of arrays.
            TreeNode root = generateTree(list, 0);
            return root;
        }

        private static TreeNode generateTree(List<int[]> list, int index)
        {
            int[] arr = new int[3] { list[index][0], list[index][1], list[index][2] }; 

            TreeNode node = new TreeNode(arr[0]);

            node.left  = arr[1] == -1 ? null : generateTree(list, arr[1]);
            node.right = arr[2] == -1 ? null : generateTree(list, arr[2]);

            return node;
        }
    }
}