Java O(N) recursive solution


  • 3
    // Encodes a tree to a single string.
        public String serialize(TreeNode root) {
            if (root == null) {
                return "*.";
            }
            StringBuilder sb = new StringBuilder();
            sb.append(root.val);
            if (root.left == null && root.right == null) {
                sb.append("*.");
                return sb.toString();
            }
            sb.append(".");
            sb.append(serialize(root.left));
            sb.append(serialize(root.right));
            return sb.toString();
        }
    
        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
            int[] begin = {0};
            return deserializeMethod(data, begin);
        }
    
        private TreeNode deserializeMethod(String data, int[] begin) {
            int index = data.indexOf(".", begin[0]);
            TreeNode node = null;
            if (data.charAt(index - 1) == '*') {
                String str = data.substring(begin[0], index - 1);
                begin[0] = index + 1;
                if (str.equals("")) {
                    return null;
                }
                node = new TreeNode(Integer.parseInt(str));
            } else {
                String str = data.substring(begin[0], index);
                begin[0] = index + 1;
                node = new TreeNode(Integer.parseInt(str));
                node.left = deserializeMethod(data, begin);
                node.right = deserializeMethod(data, begin);
            }
            return node;
        }

Log in to reply
 

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