Java solution with preorder traversal, space optimize, beat 99.29%

  • 0

    The idea is from this lecture slide.

    Use an indicator ('*') to mark internal nodes, use "n" to mark a null node. If the node is a leaf node, just add the value.

    public class Codec {
        // Encodes a tree to a single string.
        public String serialize(TreeNode root) {
            if(root == null){
                return "";
            StringBuilder sb = new StringBuilder();
            helper(sb, root);
            return sb.toString();
        public void helper(StringBuilder sb, TreeNode root){
            if(root.left == null && root.right == null){
                // if the node is an internal node, mark it value with a '*' to indicate.
                helper(sb, root.left);
                helper(sb, root.right);
        // Decodes your encoded data to tree.
        int index =0;
        public TreeNode deserialize(String data) {
                return null;
            String[] values = data.split(",");
            TreeNode root = dHelper(values);
            return root;
        public TreeNode dHelper(String[] values){
            if(index >= values.length || values[index].equals("n")){
                return null;
            String val = values[index];
            if(val.charAt(val.length()-1) =='*'){
                // means it has child;
                val = val.substring(0, val.length()-1);
                int data = Integer.parseInt(val);
                TreeNode node = new TreeNode(data);
                node.left = dHelper(values);
                node.right = dHelper(values);
                return node;
                // its the leaf
                TreeNode node = new TreeNode(Integer.parseInt(val));
                return node;

    Runtime: 12ms, beat 99.29%;

Log in to reply

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