My Iterative Solution using Queue


  • 0
    A

    /**

    • Definition for a binary tree node.

    • public class TreeNode {

    • int val;
      
    • TreeNode left;
      
    • TreeNode right;
      
    • TreeNode(int x) { val = x; }
      
    • }
      */
      public class Codec {

      ArrayList<String> serialized = new ArrayList<String>();

      // Encodes a tree to a single string.
      public String serialize(TreeNode root) {
      if(root==null){
      return "[null]";
      }

       Queue<TreeNode> myQ = new LinkedList<TreeNode>();
       StringBuilder sb = new StringBuilder();
       myQ.offer(root);
       serialized.add(Integer.toString(root.val));
       
       while(!myQ.isEmpty()){
           TreeNode temp = myQ.poll();
         //  System.out.println(temp.val);
           
           //left subtree
           if(temp.left!=null){
               //System.out.println(temp.left.val);
               myQ.offer(temp.left);
               serialized.add(Integer.toString(temp.left.val));
           }else{
               serialized.add("null");
           }
           
           //right subtree
           if(temp.right!=null){
               //System.out.println(temp.right.val);
               myQ.offer(temp.right);
               serialized.add(Integer.toString(temp.right.val));
           }else{
               serialized.add("null");
           }
       }
       
       sb.append("[");
       for(int i=0;i<serialized.size();i++){
           sb.append(serialized.get(i));
           if(i!=serialized.size()-1)
              sb.append(",");
       }
       sb.append("]");
       
       //System.out.println(sb.toString());
       
       return sb.toString();
      

      }

      // Decodes your encoded data to tree.
      public TreeNode deserialize(String data) {
      String newString = data.substring(1,data.length()-1);
      String[] tree = newString.split(",");

       //System.out.println(tree.length);
       
       if(tree.length==1 && tree[0].equals("null"))
           return null;
           
       TreeNode root = new TreeNode(Integer.parseInt(tree[0]));
       Queue<TreeNode> myQ = new LinkedList<TreeNode>();
       myQ.add(root);
       
       int i=1;
       while(!myQ.isEmpty()){
           TreeNode temp = myQ.poll();
           if(!tree[i].equals("null")){
               TreeNode left = new TreeNode(Integer.parseInt(tree[i]));
               temp.left = left;
               myQ.offer(left);
           }else{
               temp.left = null;
           }
           i++;
           
           if(!tree[i].equals("null")){
               TreeNode right = new TreeNode(Integer.parseInt(tree[i]));
               temp.right = right;
               myQ.offer(right);
           }else{
               temp.right = null;
           }
           i++;
       }
       
       return root;
      

      }
      }

    // Your Codec object will be instantiated and called as such:
    // Codec codec = new Codec();
    // codec.deserialize(codec.serialize(root));


Log in to reply
 

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