Share solution using stack for both serialization and deserialization

  • 0

    Basic idea:
    Serialization: using pre-order to complete the task, "," as the delimter
    Deserialization: keep pushing nodes into the stack, every time you push a new node,

    • if the new node is less than top of the stack, then you know the new node is the left child of top of the stack (the only case the stack is empty is when the new node is root)

    • if the new node is larger than top of the stack, then keep popping the stack until it's either empty or top of the stack is larger than the new node, now the new node is right child of the node you just popped.

    see the code:
    public String serialize(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    TreeNode node;
    if (root == null) return null;
    StringBuilder sb = new StringBuilder();
    while (!stack.isEmpty()) {
    node = stack.pop();
    sb.append(String.valueOf(node.val) + ",");
    if (node.right != null) stack.push(node.right);
    if (node.left != null) stack.push(node.left);
    if (sb.length() > 0) sb.deleteCharAt(sb.length() - 1);
    return sb.toString();

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data == null) return null;
        Stack<TreeNode> stack = new Stack<>();
        String[] s = data.split(",");
        TreeNode root = null;
        for (int i = 0; i < s.length; i++) {
            TreeNode node = new TreeNode(Integer.parseInt(s[i]));
            if (root == null) root = node;
            if (!stack.isEmpty()) {
                if (stack.peek().val > node.val) {
                    stack.peek().left = node;
                else {
                    TreeNode parent = new TreeNode(0);
                    while (!stack.isEmpty() && stack.peek().val < node.val) {
                        parent = stack.pop();
                    parent.right = node;
        return root;

Log in to reply

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