Java solution that beats 99.5% answers


  • 0
    F
    public class SerializeAndDeserializeBinaryTree {
        /**
         * This method will be invoked first, you should design your own algorithm
         * to serialize a binary tree which denote by a root node to a string which
         * can be easily deserialized by your own "deserialize" method later.
         */
        public String serialize(TreeNode root) {
            StringBuilder sb = new StringBuilder();
            _serialize(root, sb);
            return sb.toString();
        }
    
        private void _serialize(TreeNode root, StringBuilder sb) {
            if (root == null) {
                sb.append("#,");
            } else {
                sb.append(root.val);
                sb.append(",");
                _serialize(root.left, sb);
                _serialize(root.right, sb);
            }
        }
    
        /**
         * This method will be invoked second, the argument data is what exactly
         * you serialized at method "serialize", that means the data is not given by
         * system, it's given by your own serialize method. So the format of data is
         * designed by yourself, and deserialize it here as you serialize it in
         * "serialize" method.
         */
        public TreeNode deserialize(String data) {
            TreeNode dummy = new TreeNode(-1);
            _deserialize(dummy, true, data, 0);
            return dummy.left;
        }
    
        private int _deserialize(TreeNode root, boolean left, String data, int start) {
            if (start < data.length() && data.charAt(start) != '#') {
                int end = start + 1;
                while (data.charAt(end) != ',') {
                    ++end;
                }
                TreeNode node = new TreeNode(Integer.parseInt(data.substring(start, end)));
                if (left) {
                    root.left = node;
                } else {
                    root.right = node;
                }
                int deserialized = _deserialize(node, true, data, end + 1);
                return _deserialize(node, false, data, deserialized + 1);
            }
            return start + 1;
        }
    }

Log in to reply
 

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