C# solution using stack


  • 0
    M
    1. Serialize using Preorder traversal (empty node as "Null")
    2. Deserialize using two stacks one to add Left node and one for right.. every node first added to LeftStack, once left pointer assigned to a node, pop from a left stack, and add a node to right stack, once right pointer assigned popped from a right stack.
    3. Left and right stack help to assign left and right node appropriately.
    public class Codec
    {
      public String Serialize(TreeNode root)
      {
         if (root == null) return "Null";
    	 //string value = root.val + root.left + root.right;
    	 return String.Format("{0},{1},{2}",root.val, Serialize(root.left), Serialize(root.right));
      }
      
      public TreeNode Deserialize(String data)
      {
    	  if (data.Trim() == String.Empty || data == "Null")
    	  {
    		  return null;
    	  }
    	  string[] treedata = data.Split(',');
    	  
    	  Stack<TreeNode> lstack = new Stack<TreeNode>();
    	  Stack<TreeNode> rstack = new Stack<TreeNode>();
    	  int val = int.Parse(treedata[0]);
    	  TreeNode root = new TreeNode(val);
    
    	  lstack.Push(root);
    	  //bool isLeft=true;
    	  for (int i=1; i<treedata.Length; i++)
    	  {
    		  TreeNode tn = null;
    		  TreeNode current =null;
    		  if (treedata[i] != "Null")
    		  {
    		     val = int.Parse(treedata[i]);
    			 tn = new TreeNode(val);
    	  	  }
    	  
    		  if (lstack.Count >0)
    		  {
    		    current = lstack.Pop();
    		    current.left = tn;
    			if (tn != null) lstack.Push(tn);
    		    rstack.Push(current);
    		  } else if (rstack.Count >0)
    		  {
    			current = rstack.Pop();
    		    current.right = tn;
    			if (tn != null) lstack.Push(tn);
    		  }
    		  
    	  }
    	  return root;
      }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.