JAVA -- Serialize into preorder traversal with separators, O(n) for both serializing and deserializing


  • 0
    C

    The idea is to serialize the BST into its pre-order traversal. The in-order traversal of a BST will be a sorted array, thus the BST will be unique given the pre-order traversal.
    I used a stack to deserialize the BST. Each element is visited only once, so the running time is O(n).

    // standard pre-order traversal
    public String serialize(TreeNode root) {
            if (root == null) {
                return "";
            }
            TreeNode node = root;
            StringBuilder sb = new StringBuilder();
            Stack<TreeNode> stack = new Stack<>();
            while (!stack.isEmpty() || node != null) {
                while (node != null) {
                    stack.push(node);
                    sb.append(node.val).append('#');
                    node = node.left;
                }
                node = stack.pop();
                node = node.right;
            }
            return sb.toString();
        }
    
        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
            TreeNode root = null;
            if (data == null || data.length() == 0) {
                return root;
            }
            String[] charArray = data.split("#");
            Stack<TreeNode> stack = new Stack<>();
            for (String c : charArray) {
                int curr = Integer.parseInt(c);
                TreeNode currNode = new TreeNode(curr);
                // the stack is only empty when currNode is the root (first element in pre-order traversal)
                if (stack.isEmpty()) {
                    root = currNode;
                }
                // if curr value is less than the last one in the stack, we are in the left subtree
                else if (curr < stack.peek().val) {
                    stack.peek().left = currNode;
                }
                // Now we are in the right subtree, the nodes in the stack with value less than curr are all in the left subtree. We are looking for the root for this right subtree, and it will be the last node with val less than curr.
                else {
                    TreeNode pre = null;
                    while (!stack.isEmpty() && stack.peek().val < curr) {
                        pre = stack.pop();
                    }
                    pre.right = currNode;
                }
                stack.push(currNode);
            }
            return root;
        }
    

Log in to reply
 

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