My 10 ms recursive Java solution


  • 0
    L

    /**

    • Definition for a binary tree node.

    • public class TreeNode {

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

      public static void serialize(TreeNode root, StringBuilder strBuilder) {
      if (root == null) return;
      strBuilder.append("(");
      if (root != null) {
      strBuilder.append(root.val);
      }
      strBuilder.append(",");
      if (root.left != null) {
      serialize(root.left, strBuilder);
      } else {
      strBuilder.append("n");
      }
      strBuilder.append(",");
      if (root.right != null) {
      serialize(root.right, strBuilder);
      } else {
      strBuilder.append("n");
      }
      strBuilder.append(")");
      }

      // Encodes a tree to a single string.
      public String serialize(TreeNode root) {
      StringBuilder strBuilder = new StringBuilder();
      serialize(root, strBuilder);
      return strBuilder.toString();
      }

      public static class RetVar {
      public TreeNode node;
      public int ptr;
      public RetVar(TreeNode node, int ptr) {
      this.node = node;
      this.ptr = ptr;
      }
      }

      public static RetVar deserialize(String data, int ptr) {
      char ch;
      int curPos = 0;
      int stPos=ptr;
      int type = 0;
      TreeNode newNode = new TreeNode(0);
      while(data.charAt(ptr++) != ')') {
      ch = data.charAt(ptr - 1);
      if(ch==',') {
      if (curPos == 0) {
      newNode.val = Integer.parseInt(data.substring(stPos, ptr - 1));
      }
      curPos++;
      } else if (ch == 'n') {
      continue;
      } else if (ch == '(') {
      RetVar retVal = deserialize(data, ptr);
      if (curPos == 1) {
      newNode.left = retVal.node;
      } else {
      newNode.right = retVal.node;
      }
      ptr = retVal.ptr;
      }
      }
      return new RetVar(newNode, ptr);
      }

      // Decodes your encoded data to tree.
      public TreeNode deserialize(String data) {
      if (data.length() == 0) return null;
      RetVar retVal = deserialize(data.substring(1), 0);
      return retVal.node;
      }
      }

    // 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.