297. Serialize deserialize tree

297_solution1.c

#include "tree_node.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// constraint: at most 10^4 nodes, values in [-1000, 1000] -> at most "-1000#"
// per node plus "N#" for each of the (nodes + 1) null children
#define MAX_NODES 10000
#define MAX_LEN (MAX_NODES * 6 + (MAX_NODES + 1) * 2 + 1)

static void serDfs(struct TreeNode *root, char *ser, int *len) {
  if (!root) {
    *len += sprintf(ser + *len, "N#");
    return;
  }
  *len += sprintf(ser + *len, "%d#", root->val);
  serDfs(root->left, ser, len);
  serDfs(root->right, ser, len);
}

char *serialize(struct TreeNode *root) {
  char *ser = malloc(MAX_LEN);
  int len = 0;
  ser[0] = '\0';
  serDfs(root, ser, &len);
  return ser;
}

static struct TreeNode *desDfs(const char *data, int *pos) {
  const char *tok = data + *pos;
  *pos = strchr(tok, '#') - data + 1; // move cursor past '#'

  if (*tok == 'N')
    return NULL;

  struct TreeNode *root = malloc(sizeof(struct TreeNode));
  root->val = atoi(tok);           // atoi stops at '#'
  root->left = desDfs(data, pos);  // advances pos past the left subtree
  root->right = desDfs(data, pos); // continues from there
  return root;
}

struct TreeNode *deserialize(char *data) {
  int pos = 0;
  return desDfs(data, &pos);
}

tree_node.h

#pragma once

#include <stddef.h>

// Definition for a binary tree node.
struct TreeNode {
  int val;
  struct TreeNode *left;
  struct TreeNode *right;
};

297_solution1.cpp

#include "tree_node.h"
#include <string>

using namespace std;

class Codec {
public:
  string serialize(TreeNode *root) {
    string ser;
    serDfs(root, ser);
    return ser;
  }

  void serDfs(TreeNode *root, string &ser) {
    if (!root) {
      ser += "N#";
      return;
    }
    ser += to_string(root->val) + "#";
    serDfs(root->left, ser);
    serDfs(root->right, ser);
  }

  TreeNode *deserialize(string data) {
    int pos = 0;
    return desDfs(data, pos);
  }

  TreeNode *desDfs(const string &data, int &pos) {
    int end = data.find('#', pos); // next delimiter
    string tok = data.substr(pos, end - pos);
    pos = end + 1; // move cursor past '#'

    if (tok == "N")
      return nullptr;

    TreeNode *root = new TreeNode(stoi(tok));
    root->left = desDfs(data, pos);  // advances pos past the left subtree
    root->right = desDfs(data, pos); // continues from there
    return root;
  }
};

tree_node.h

#pragma once

// Definition for a binary tree node.
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right)
      : val(x), left(left), right(right) {}
};

297_solution1.go

package trees

import (
    "strconv"
    "strings"
)

type Codec struct{}

func Constructor() Codec {
    return Codec{}
}

func (c *Codec) serialize(root *TreeNode) string {
    var sb strings.Builder

    var dfs func(node *TreeNode)
    dfs = func(node *TreeNode) {
        if node == nil {
            sb.WriteString("N#")
            return
        }
        sb.WriteString(strconv.Itoa(node.Val) + "#")
        dfs(node.Left)
        dfs(node.Right)
    }

    dfs(root)
    return sb.String()
}

func (c *Codec) deserialize(data string) *TreeNode {
    tokens := strings.Split(data, "#")
    pos := 0

    var dfs func() *TreeNode
    dfs = func() *TreeNode {
        tok := tokens[pos]
        pos++

        if tok == "N" {
            return nil
        }

        val, _ := strconv.Atoi(tok)
        node := &TreeNode{Val: val}
        node.Left = dfs()  // advances pos past the left subtree
        node.Right = dfs() // continues from there
        return node
    }

    return dfs()
}

tree_node.go

package trees

// Definition for a binary tree node.
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

297_solution1.java

public class Codec {
    private int pos;

    public String serialize(TreeNode root) {
        StringBuilder ser = new StringBuilder();
        serDfs(root, ser);
        return ser.toString();
    }

    private void serDfs(TreeNode node, StringBuilder ser) {
        if (node == null) {
            ser.append("N#");
            return;
        }
        ser.append(node.val).append('#');
        serDfs(node.left, ser);
        serDfs(node.right, ser);
    }

    public TreeNode deserialize(String data) {
        pos = 0;
        return desDfs(data);
    }

    private TreeNode desDfs(String data) {
        int end = data.indexOf('#', pos); // next delimiter
        String tok = data.substring(pos, end);
        pos = end + 1; // move cursor past '#'

        if (tok.equals("N"))
            return null;

        TreeNode node = new TreeNode(Integer.parseInt(tok));
        node.left = desDfs(data);  // advances pos past the left subtree
        node.right = desDfs(data); // continues from there
        return node;
    }
}

TreeNode.java

// Definition for a binary tree node.
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {}

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

297_solution1.js

const TreeNode = require("./tree_node");

var serialize = function (root) {
  const ser = [];

  const dfs = (node) => {
    if (!node) {
      ser.push("N#");
      return;
    }
    ser.push(node.val + "#");
    dfs(node.left);
    dfs(node.right);
  };

  dfs(root);
  return ser.join("");
};

var deserialize = function (data) {
  const tokens = data.split("#");
  let pos = 0;

  const dfs = () => {
    const tok = tokens[pos++];
    if (tok === "N") return null;

    const node = new TreeNode(Number(tok));
    node.left = dfs(); // advances pos past the left subtree
    node.right = dfs(); // continues from there
    return node;
  };

  return dfs();
};

tree_node.js

// Definition for a binary tree node.
function TreeNode(val, left, right) {
  this.val = val === undefined ? 0 : val;
  this.left = left === undefined ? null : left;
  this.right = right === undefined ? null : right;
}

module.exports = TreeNode;

297_solution1.py

from typing import Optional

from tree_node import TreeNode


class Codec:
    def serialize(self, root: Optional[TreeNode]) -> str:
        ser = []

        def dfs(node: Optional[TreeNode]) -> None:
            if not node:
                ser.append("N#")
                return
            ser.append(f"{node.val}#")
            dfs(node.left)
            dfs(node.right)

        dfs(root)
        return "".join(ser)

    def deserialize(self, data: str) -> Optional[TreeNode]:
        tokens = iter(data.split("#"))

        def dfs() -> Optional[TreeNode]:
            tok = next(tokens)
            if tok == "N":
                return None

            node = TreeNode(int(tok))
            node.left = dfs()  # consumes the left subtree's tokens
            node.right = dfs()  # continues from there
            return node

        return dfs()

tree_node.py

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

297_solution1.rs

use std::cell::RefCell;
use std::rc::Rc;

use crate::tree_node::TreeNode;

type Link = Option<Rc<RefCell<TreeNode>>>;

struct Codec {}

impl Codec {
    fn new() -> Self {
        Codec {}
    }

    fn serialize(&self, root: Link) -> String {
        let mut ser = String::new();
        Self::ser_dfs(&root, &mut ser);
        ser
    }

    fn ser_dfs(node: &Link, ser: &mut String) {
        match node {
            None => ser.push_str("N#"),
            Some(n) => {
                let n = n.borrow();
                ser.push_str(&format!("{}#", n.val));
                Self::ser_dfs(&n.left, ser);
                Self::ser_dfs(&n.right, ser);
            }
        }
    }

    fn deserialize(&self, data: String) -> Link {
        let mut tokens = data.split('#');
        Self::des_dfs(&mut tokens)
    }

    fn des_dfs<'a>(tokens: &mut impl Iterator<Item = &'a str>) -> Link {
        let tok = tokens.next()?;
        if tok == "N" {
            return None;
        }

        let mut node = TreeNode::new(tok.parse().unwrap());
        node.left = Self::des_dfs(tokens); // consumes the left subtree's tokens
        node.right = Self::des_dfs(tokens); // continues from there
        Some(Rc::new(RefCell::new(node)))
    }
}

tree_node.rs

use std::cell::RefCell;
use std::rc::Rc;

// Definition for a binary tree node.
#[derive(Debug, PartialEq, Eq)]
pub struct TreeNode {
    pub val: i32,
    pub left: Option<Rc<RefCell<TreeNode>>>,
    pub right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    #[inline]
    pub fn new(val: i32) -> Self {
        TreeNode {
            val,
            left: None,
            right: None,
        }
    }
}