Save half the space in best case


  • 0
    L

    The idea is to perform level order traversal (like how leetcode serialize trees), but do not store the null pointer explicitly for the last level. In case the tree is a complete tree and each node on the last level are there, we can save half the space by eliminating the null pointers for the last level.

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Codec {
    
        // Encodes a tree to a single string.
        public String serialize(TreeNode root) {
    		StringBuilder sb = new StringBuilder();
    		if (root == null) {
    			return sb.toString();
    		}
    
    		Queue<TreeNode> queue = new LinkedList<>();
    		queue.offer(root);
    		int curLevel = 1;
    		boolean isLastLevel = false;
    		if (root.left == null && root.right == null) {
    			isLastLevel = true;
    		}
    
    		boolean hasGrandChildren = false;
    		while (!queue.isEmpty()) {
    			TreeNode cur = queue.poll();
    			curLevel -= 1;
    			if (cur == null) {
    				sb.append("#").append(",");
    			} else {
    				sb.append(cur.val).append(",");
    
    				if (cur.left != null) {
    					queue.offer(cur.left);
    					if (cur.left.left != null || cur.left.right != null) {
    						hasGrandChildren = true;
    					}
    				} else if (!isLastLevel) {
    					queue.offer(cur.left);
    				}
    
    				if (cur.right != null) {
    					queue.offer(cur.right);
    					if (cur.right.left != null || cur.right.right != null) {
    						hasGrandChildren = true;
    					}
    				} else if (!isLastLevel) {
    					queue.offer(cur.right);
    				}
    			}
    
    			if (curLevel == 0) {
    				curLevel = queue.size();
    				isLastLevel = !hasGrandChildren;
    				hasGrandChildren = false;
    			}
    		}
    		sb.setLength(sb.length() - 1);
    		return sb.toString();
        }
    
        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
            if (data == null || data.length() == 0) {
                return null;
            }
            
            String[] dataArr = data.split(",");
            int n = dataArr.length;
            Queue<TreeNode> queue = new LinkedList<>();
            TreeNode root = createNode(dataArr[0]);
            TreeNode cur = root;
            boolean leftAdded = false;
            boolean rightAdded = false;
            for (int i = 1; i < n; i++) {
                if (!leftAdded) {
                    cur.left = createNode(dataArr[i]);
                    if (cur.left != null) {
                        queue.offer(cur.left);
                    }
                    leftAdded = true;
                } else if (!rightAdded) {
                    cur.right = createNode(dataArr[i]);
                    if (cur.right != null) {
                        queue.offer(cur.right);
                    }
                    rightAdded = true;
                } else {
                    cur = queue.poll();
                    leftAdded = false;
                    rightAdded = false;
                    i -= 1;
                }
            }
            return root;
        }
        
        private TreeNode createNode(String s) {
            if (s.equals("#")) {
                return null;
            } else {
                return new TreeNode(Integer.parseInt(s));
            }
        }
    }
    
    // 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.