Java Easy Solution beats 84.41% without recursion


  • 0
    C
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Codec {
        private static final String SPLIT_FLAG = ",";
        private int deseIndex = 0;
    
        // Encodes a tree to a single string.
        public String serialize(TreeNode root) {
            StringBuilder str = new StringBuilder();
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            TreeNode cur;
            while (!queue.isEmpty()){
                cur = queue.poll();
                if (cur != null){
                    str.append(cur.val);
                    queue.offer(cur.left);
                    queue.offer(cur.right);
                } 
                str.append(SPLIT_FLAG);
            }
            return str.toString();
        }
    
        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
            deseIndex = 0;
            if (data.length() == 0){
                return null;
            } else {
                Queue<TreeNode> queue = new LinkedList<>();
                TreeNode root = getNextNode(data);
                if (root != null)
                    queue.offer(root);
                TreeNode cur = null;
                int index = 1;
                while (!queue.isEmpty()){
                    cur = queue.poll();
                    cur.left = getNextNode(data);
                    cur.right = getNextNode(data);
                    if (cur.left != null)
                        queue.offer(cur.left);
                    if (cur.right != null)
                       queue.offer(cur.right); 
                }
                return root;
            }
        }
        private TreeNode getNextNode(String str){
            int start = deseIndex;
            int value = 0;
            char cur;
            while (deseIndex < str.length()){
                cur = str.charAt(deseIndex++);
                if (cur == ','){
                    break;
                } else {
                    value *= 10;
                    value += cur - '0';
                }
            }
            if (deseIndex == start + 1)
                return null;
            else
                return new TreeNode(value);
        }
    }
    
    // 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.