Using stack to serialize and deserialize a BST


  • 0
    F

    We have already known the inorder traversal of a BST, then we only need to save preorder traversal of the BST to do the reconstruction.

    public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode node = root;
        
        while (node != null || !stack.isEmpty()) {
            if (node != null) {
                sb.append(node.val + ";");
                stack.push(node);
                node = node.left;
            } else {
                node = stack.pop();
                node = node.right;
            }
        }
        
        return (sb.toString());
    }
    
    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data.equals("")) {
            return (null);
        }
        
        String[] preorder = data.split(";");
        Stack<TreeNode> stack = new Stack<>();
        TreeNode root = null;
        
        for (int i = 0; i < preorder.length; i++) {
            int val = Integer.parseInt(preorder[i]);
            
            if (stack.isEmpty()) {
                /*
                 * When the stack is empty, create the root node.
                 */
                root = new TreeNode(val);
                stack.push(root);
            } else if (val < stack.peek().val) {
                /*
                 * When current value is smaller than the value of top node in the stack,
                 * create left child of top node and push its left child to the stack.
                 */
                stack.peek().left = new TreeNode(val);
                stack.push(stack.peek().left);
            } else {
                /*
                 * When current value is not smaller than the value of top node in the stack,
                 * find the first node whose parent's value is larger than the value,
                 * create right child of the node and push its right child to the stack.
                 */
                TreeNode node = stack.pop();
    
                while (!stack.isEmpty() && stack.peek().val < val) {
                    node = stack.pop();
                }
                
                node.right = new TreeNode(val);
                stack.push(node.right);
            }
        }
    
        return (root);
    }
    

    }


Log in to reply
 

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