Deserialize from preorder and computed inorder, reusing old solution


  • 17

    I serialize the tree's values in preorder. For deserializing, I additionally compute inorder simply by sorting the preorder. And then I just use the buildTree function that I copied&pasted from my old solution for the old problem Construct Binary Tree from Preorder and Inorder Traversal.

    class Codec:
    
        def serialize(self, root):
            def preorder(node):
                if node:
                    vals.append(str(node.val))
                    preorder(node.left)
                    preorder(node.right)
            vals = []
            preorder(root)
            return ' '.join(vals)
    
        def deserialize(self, data):
            preorder = map(int, data.split())
            inorder = sorted(preorder)
            return self.buildTree(preorder, inorder)
    
        def buildTree(self, preorder, inorder):
            def build(stop):
                if inorder and inorder[-1] != stop:
                    root = TreeNode(preorder.pop())
                    root.left = build(root.val)
                    inorder.pop()
                    root.right = build(stop)
                    return root
            preorder.reverse()
            inorder.reverse()
            return build(None)
    

    (I had seen @shallpion's title saying "preorder" before thinking about this problem, so can't be sure I would've had the idea myself, though I think I would've.)


  • 1
    K

    +1 Yes, utilizing BST property, this encoding scheme is more compact as considering in-between NULL nodes can be avoided. Thanks.


  • 0

    U can just construct a BST from preorder alone.


  • 0

    @xruzty Well I do construct it from preorder alone. Preorder is all that my deserialize function gets. But yeah, I guess I could do it without computing the inorder first. I had actually started on that but then realized I could just be lazy and do the above. And I like it :-)


  • 0

    Java version based on the same idea:

    • Serialization: generate space separated pre-order traversal string
    • Deserialization: get in-order traversal string by sorting & generate the tree based on in-order and pre-order sequences
    // Encodes a tree to a single string.
        public static String serialize(TreeNode root) {
            if (root == null) return null;
            // pre-order traversal
            StringBuilder sb = new StringBuilder();
            preOrderRecurs(root, sb);
            sb.deleteCharAt(sb.length() - 1);
            return sb.toString();
        }
    
        private static void preOrderRecurs(TreeNode node, StringBuilder sb) {
            if (node != null) {
                sb.append(node.val + " ");
    
                preOrderRecurs(node.left, sb);
                preOrderRecurs(node.right, sb);
            }
        }
    
        // Decodes your encoded data to tree.
        public static TreeNode deserialize(String data) {
            if (data == null) return null;
            // get in order traversal by sorting
            String[] array = data.split("\\s");
            int[] preOrder = new int[array.length];
            for (int i = 0; i < array.length; i++) {
                preOrder[i] = Integer.parseInt(array[i]);
            }
            int[] inOrder = Arrays.copyOf(preOrder, preOrder.length);
            Arrays.sort(inOrder);
    
            return recurs(inOrder, preOrder, 0, inOrder.length - 1, 0, preOrder.length - 1);
        }
    
        private static TreeNode recurs(int[] inorder, int[] preorder, int inStart, int inEnd, int preStart, int preEnd) {
            if (inStart < 0 || inEnd < 0 || inEnd >= inorder.length || inStart > inEnd || preStart < 0 || preEnd < 0
                || preEnd >= preorder.length || preStart > preEnd) {
                return null;
            }
            int topValue = preorder[preStart];
            TreeNode topNode = new TreeNode(topValue);
            int topIndex = findTopIndex(inorder, inStart, inEnd, topValue);
            int leftItems = topIndex - inStart;
            int rightItems = inEnd - topIndex;
            TreeNode leftNode = recurs(inorder, preorder, inStart, topIndex - 1, preStart + 1, preStart + leftItems);
            TreeNode rightNode = recurs(inorder, preorder, topIndex + 1, inEnd, preEnd - rightItems + 1, preEnd);
            topNode.left = leftNode;
            topNode.right = rightNode;
            return topNode;
        }
    
        private static int findTopIndex(int[] array, int start, int end, int value) {
            for (int i = start; i <= end; i++) {
                if (value == array[i]) {
                    return i;
                }
            }
            return -1;
        }
    

  • 0
    • Serialize by Generating comma seperated preorder traversal
    void preorder(TreeNode* root, string& s){
        if(!root)
            return;
        s = s + to_string(root->val) + ",";
        preorder(root->left,s);
        preorder(root->right,s);
    }
    string serialize(TreeNode* root) {
        string s;
        if(!root)
            return s;
        preorder(root,s);
        return s;
    }
    
    • Build the BST with the given preorder traversal. (There can be only 1 unique BST for a given preorder traversal) works for postorder too!
    TreeNode* construct(vector<int>& A, int* i, int l, int r){
        if(*i>=A.size())
            return NULL;
        int key = A[*i];
        if(key<=l || key>=r)
            return NULL;
        *i = *i + 1;
        TreeNode* root = new TreeNode(key);
        root->left = construct(A,i,l,key);
        root->right = construct(A,i,key,r);
        return root;
    }
    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        int n = data.size();
        if(!n)
            return NULL;
        istringstream ss(data);
        int c; string s;
        vector<int> A;
        while(getline(ss,s,',')){
            istringstream t(s);
            t>>c;
            A.push_back(c);
        }
        c = 0;
        int *i= &c;
        return construct(A,i,INT_MIN,INT_MAX);
    }

  • 1

    Note:
    You may assume that duplicates do not exist in the tree.

    Do you limited to the above condition when u construct from in-order and pre-order?


  • 0
    K
    // Encodes a tree to a single string.
        public static String serialize(TreeNode root) {
            if (root == null) return null;
            // pre-order traversal
            StringBuilder sb = new StringBuilder();
            preOrderRecurs(root, sb);
            sb.deleteCharAt(sb.length() - 1);
            return sb.toString();
        }
    
        private static void preOrderRecurs(TreeNode node, StringBuilder sb) {
            if (node != null) {
                sb.append(node.val + " ");
    
                preOrderRecurs(node.left, sb);
                preOrderRecurs(node.right, sb);
            }
        }
    
        // Decodes your encoded data to tree.
        public static TreeNode deserialize(String data) {
            if (data == null) return null;
            // get in order traversal by sorting
            String[] array = data.split("\\s");
            int[] preOrder = new int[array.length];
            for (int i = 0; i < array.length; i++) {
                preOrder[i] = Integer.parseInt(array[i]);
            }
            int[] inOrder = Arrays.copyOf(preOrder, preOrder.length);
            Arrays.sort(inOrder);
            
            Map<Integer, Integer> map = new HashMap<Integer, Integer>();
            
            for(int i=0; i < inOrder.length; i++) {
                map.put(inOrder[i],i);
            }
    
            return recurs(inOrder, preOrder, 0, inOrder.length - 1, 0, preOrder.length - 1, map);
            
        }
    
        private static TreeNode recurs(int[] inorder, int[] preorder, int inStart, int inEnd, int preStart, int preEnd, Map<Integer,Integer> map) {
            if (inStart < 0 || inEnd < 0 || inEnd >= inorder.length || inStart > inEnd || preStart < 0 || preEnd < 0
                || preEnd >= preorder.length || preStart > preEnd) {
                return null;
            }
            int rootValue = preorder[preStart];
            TreeNode root = new TreeNode(rootValue);
            int middle = map.get(rootValue);
            int leftItems = middle - inStart;
            root.left  = recurs(inorder, preorder, inStart, middle - 1, preStart + 1, preStart + leftItems, map);
            root.right = recurs(inorder, preorder, middle + 1, inEnd, preStart + leftItems + 1, preEnd, map);
            return root;
        }
    }
    

  • 2
    R

    I have slightly modified your buildTree function

    def buildTree(self,preorder,inorder):
            if inorder:
                index = inorder.index(preorder.pop(0))
                root = TreeNode(inorder[index])
                root.left = self.buildTree(preorder,inorder[:index])
                root.right = self.buildTree(preorder,inorder[index+1:])
                return root
    

  • 1
    M

    The below JAVA code is based on a similar idea. Uses:

    1. preorder during serialization.
    2. boundry of the preorder subtree during deserialization
                   //PreOder
    		public String serialize(TreeNode root) {
    			StringBuilder sb = new StringBuilder();
    			Stack<TreeNode> stk = new Stack<>();
    			if (root != null) stk.push(root);
    			TreeNode curr = null;
    			while (!stk.isEmpty()) {
    				curr = stk.pop();
    				sb.append(",").append(curr.val);
    				if (curr.right != null)	stk.push(curr.right);
    				if (curr.left != null) stk.push(curr.left);
    			}
    			String string = sb.toString();
    			return string.isEmpty() ? null : string.substring(1);
    		}
    
    		// Decodes your encoded data to tree.
    		public TreeNode deserialize(String data) {
    			if (data == null || data.length() == 0) return null;
    			String[] nodes = data.split(",");
    			if (nodes == null || nodes.length == 0) return null;
    
    			List<Integer> q = new ArrayList<>();
    			for (String node : nodes) {
    				int val = Integer.parseInt(node);
    				q.add(val);
    			}
    			return decodeTree(0, q.size() - 1, q);
    		}
    		
    		// use the end index as the boundry of subtree in preOrder Traversal
    		private TreeNode decodeTree(int rootIndex, int end, List<Integer> q) {
    			if (q.isEmpty() || rootIndex >= q.size() || rootIndex > end) return null;
    
    			TreeNode root = new TreeNode(q.get(rootIndex));
    			int curr = rootIndex + 1;
    			while (curr <= end && q.get(curr) < root.val) curr++;
    			if (curr > end)
    				root.left = decodeTree(rootIndex + 1, end, q);
    			else 	{
    			    root.left = decodeTree(rootIndex + 1, curr - 1, q);
    			    root.right = decodeTree(curr, end, q);
    			}
    			return root;
    		}
    '''

  • 1
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root == null) return null;
        
        String left = serialize(root.left);
        String right = serialize(root.right);
        if(left == null && right == null) return root.val+"";
    
        StringBuilder sb = new StringBuilder();
        sb.append(root.val);
        if(left != null) sb.append(","+left);
        if(right != null) sb.append(","+right);
        
        return sb.toString();
    }
    
    
    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data == null) return null;
        String[] nodeStrings = data.split(",");
        int[] nodes = new int[nodeStrings.length];
        int i = 0;
        for(String node : nodeStrings) {
            nodes[i++] = Integer.parseInt(node);
        }
        return deserialize(nodes, 0, nodes.length-1);
    }
    
    private TreeNode deserialize(int[] nodes, int start, int end) {
        if(start > end) return null;
        if(start == end) return new TreeNode(nodes[start]);
    
        int leftEnd = start, rightBegin = start+1;
    
        TreeNode root = new TreeNode(nodes[start]);
        for(int i = start+1; i <= end; i++) {
            if(nodes[i] > root.val) break;
            leftEnd = i;
            rightBegin = leftEnd+1;
        }
        
        root.left = deserialize(nodes, start+1, leftEnd);
        root.right = deserialize(nodes, rightBegin, end);
        return root;
    }

  • 0
    L

    @StefanPochmann

    Hey Stefan, why can't we encode the BST using BFS? Then we can find each child of a node in the string using 2i +1 and 2i+2. When decoding, we can store nodes in a hashmap if they have a parent. So when we iterate through the string, we check if they have a parent, if so we retrieve that node from our map and set its children.

    I tried this but my solution is missing null values. I don't quite understand though because everything should be null by default, and only the things I set should be there.


  • 0

    @lean3 BFS should work. I don't understand your description, though.


  • 0
    B

    @三千世界 This solution works, even if the duplicates exist in the tree. Because in_ order of BST is sorted, the duplicates are together. We can modified the code based on the definition of BST in this question.


  • 0
    D

    @StefanPochmann Initially I also thought of the same solution but I realized that you can use this trick (constructing binary tree from pre+in order traversal) only when there are no duplicates. You can check the #105 and #106 description.


  • 0
    K

    @StefanPochmann said in Deserialize from preorder and computed inorder, reusing old solution:

    inorder
    what is the time complexity compare with using the old way?


Log in to reply
 

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