Advertisement
rishu110067

Untitled

Jan 24th, 2022
870
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2.  
  3. public class Codec
  4. {
  5.     // Encodes a tree to a single string.
  6.     public string serialize(TreeNode root)
  7.     {
  8.         if(root == null)
  9.             return string.Empty;
  10.  
  11.         System.Text.StringBuilder output = new System.Text.StringBuilder();
  12.         Queue<TreeNode> q = new Queue<TreeNode>();
  13.         q.Enqueue(root);
  14.         output.Append(root.val);
  15.         output.Append(','); // append ',' to separate node.values in the string
  16.        
  17.         while(q.Count > 0)
  18.         {
  19.             var node = q.Dequeue();                        
  20.  
  21.             if(node.left != null)
  22.             {
  23.                 q.Enqueue(node.left);
  24.                 output.Append(node.left.val);
  25.                 output.Append(',');
  26.             }
  27.             else
  28.             {
  29.                 output.Append('n');
  30.                 output.Append(',');
  31.             }
  32.  
  33.             if(node.right != null)
  34.             {
  35.                 q.Enqueue(node.right);
  36.                 output.Append(node.right.val);
  37.                 output.Append(',');
  38.             }
  39.             else
  40.             {
  41.                 output.Append('n');
  42.                 output.Append(',');
  43.             }
  44.         }
  45.  
  46.         return output.ToString();
  47.     }
  48.  
  49.  
  50.     // Decodes your encoded data to tree.
  51.     public TreeNode deserialize(string data)
  52.     {
  53.         if(string.IsNullOrEmpty(data))
  54.             return null;
  55.  
  56.         int nullValue = 1001; // Node.value <= 1000 so we can assign 1001 to null
  57.        
  58.         // Convert data into a list
  59.         List<int> dataList = new List<int>();
  60.         int i = 0;
  61.         while(i < data.Length)
  62.         {
  63.             if(data[i] == 'n')
  64.             {
  65.                 dataList.Add(nullValue);
  66.                 i+=2;
  67.                 continue;
  68.             }
  69.            
  70.             int sign = 1;
  71.             if(data[i] == '-')
  72.             {
  73.                 sign = -1;
  74.                 i++;
  75.             }
  76.             int num = 0;
  77.             while(data[i] != ',')
  78.             {
  79.                 num = num * 10 + Convert.ToInt32(data[i].ToString());
  80.                 i++;
  81.             }
  82.             dataList.Add(sign * num);
  83.             i++;
  84.         }
  85.        
  86.         TreeNode root = new TreeNode(dataList[0]);
  87.         Queue<TreeNode> q = new Queue<TreeNode>();
  88.         q.Enqueue(root);
  89.         int index = 0;
  90.         while(q.Count > 0)
  91.         {
  92.  
  93.             var node = q.Dequeue();
  94.             if(index + 2 < data.Length)
  95.             {
  96.                 var left = dataList[index + 1];
  97.                 var right = dataList[index + 2];
  98.                 if(left != nullValue)
  99.                 {
  100.                     TreeNode leftNode = new TreeNode(left);
  101.                     node.left = leftNode;
  102.                     q.Enqueue(node.left);
  103.                 }
  104.                 else
  105.                 {
  106.                     TreeNode leftNode = null;
  107.                     node.left = leftNode;              
  108.                 }
  109.  
  110.                 if(right != nullValue)
  111.                 {
  112.                     TreeNode rightNode = new TreeNode(right);
  113.                     node.right = rightNode;
  114.                     q.Enqueue(node.right);
  115.                 }
  116.                 else
  117.                 {
  118.                     TreeNode rightNode = null;
  119.                     node.right = rightNode;
  120.                 }
  121.  
  122.                 index = index + 2;
  123.             }
  124.         }
  125.  
  126.         return root;
  127.     }
  128. }
  129.  
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement