Can someone tell me why i am getting the Time Limited Exceeded


  • 0
    P

    /**

    • Definition for a binary tree node.

    • public class TreeNode {

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

      // Encodes a tree to a single string.
      public String serialize(TreeNode root) {
      if(root==null)return "";
      LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
      queue.addLast(root);
      String ans ="";
      while(!queue.isEmpty()){
      TreeNode par = queue.removeFirst();
      if(par!=null){
      ans += Integer.toString(par.val) + ",";
      queue.addLast(par.left);
      queue.addLast(par.right);
      }
      else{
      ans += "null," ;
      }
      }
      return ans.substring(0,ans.length()-1);
      }

      // Decodes your encoded data to tree.
      public TreeNode deserialize(String data) {
      if(data==null || data=="") return null;
      String[] node = data.split(",");
      if(node.length==1)return new TreeNode(Integer.parseInt(node[0]));

      LinkedList<TreeNode> nodes = new LinkedList<TreeNode>();
      TreeNode root = new TreeNode(Integer.parseInt(node[0]));
      nodes.addLast(root);
      int i=1;
      int len = node.length;
      while(i<len){
      	String val1 = node[i];
      	String val2 = node[i+1];
      	TreeNode t1 = (val1.equals("null"))?null:new TreeNode(Integer.parseInt(val1));
      	TreeNode t2 = (val2.equals("null"))?null:new TreeNode(Integer.parseInt(val2));
      	TreeNode p = nodes.removeFirst();
      	if(p!=null){
      		p.left = t1;
      		p.right = t2;
      	}
      	if(t1!=null)nodes.addLast(t1);
      	if(t2!=null)nodes.addLast(t2);
      	i=i+2;
      }
      return root;
      

      }
      }

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


  • 3
    L

    It turns out that your algorithm is correct, but you are concatenating strings in an inefficient way.
    Keep in mind, if you have m strings to concatenate, and assume each string has O(1) size. Then applying String's "+=" operations m times indeed takes O(m^2) time since String is immutable.
    To solve this problem, simply use StringBuilder or StringBuffer to achieve linear concatenation time.

    StringBuilder ans = new StringBuilder();
    while(!queue.isEmpty()){
        TreeNode par = queue.removeFirst();
        if(par!=null){
            ans.append(Integer.toString(par.val) + ",");
            queue.addLast(par.left);
            queue.addLast(par.right);
        }
        else{
            ans.append("null,");
        }
    }
    return ans.toString().substring(0,ans.length()-1);

  • 0
    L

    I have changed your code by using StringBuilder instead, and got AC.


Log in to reply
 

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