#toyprogrammingchallenge
#python Here's another freebie, I assume it is python specific because they start with a base of python code. But if it makes sense, try it in whatever language you like:
This problem was asked by Google.
Given the root to a binary tree, implement serialize(root), which serializes the tree into a string, and deserialize(s), which deserializes the string back into the tree.
For example, given the following Node class
class Node:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right
The following test should pass:
node = Node('root', Node('left', Node('left.left')), Node('right'))
assert deserialize(serialize(node)).left.left.val == 'left.left'
Octave solution
function self = node(val, left = [], right = [])
self.val = val;
self.left = left;
self.right = right; end;
function escaped = escape_chars(raw)
escaped = regexprep(raw, '([\\\(\),])', '\\$1'); end;
function raw = unescape_chars(escaped)
i = 1;
while i < numel(escaped)
if escaped(i) == '\'
escaped = escaped([1:(i - 1) (i + 1):end]); end;
i++; end;
raw = escaped; end
function index = val_extent(string)
special_chars = strchr(string, '(,)');
if isempty(special_chars)
index = 0;
else
is_backslash = string == '\';
for i = special_chars
is_escaped = false;
for j = (i - 1):-1:1
if is_backslash(j)
is_escaped = ~is_escaped;
else
break; end; end;
if ~is_escaped
break; end; end;
index = i; end; end;
function string = serialize(tree)
if isempty(tree)
string = [];
elseif isempty(tree.left) && isempty(tree.right)
string = escape_chars(tree.val);
else
string = [escape_chars(tree.val) '(' serialize(tree.left) ',' serialize(tree.right) ')']; end; end
function [node, leftover] = deserialize(string)
next_special = val_extent(string);
if next_special == 0
node.val = unescape_chars(string);
node.left = [];
node.right = [];
leftover = [];
elseif string(next_special) == '('
node.val = unescape_chars(string(1:(next_special - 1)));
leftover = string((next_special + 1):end);
[node.left, leftover] = deserialize(leftover);
[node.right, leftover] = deserialize(leftover);
else
if next_special == 1
node = [];
else
node.val = unescape_chars(string(1:(next_special - 1)));
node.left = [];
node.right = []; end
if string(next_special) == ','
leftover = string((next_special + 1):end);
else
leftover = string((next_special + 2):end); end; end; end;
Better deserialize()
function indices = control_chars(string)
special_chars = strchr(string, '(,)');
indices = [];
if ~isempty(special_chars)
is_backslash = string == '\';
for i = special_chars
is_escaped = false;
for j = (i - 1):-1:1
if is_backslash(j)
is_escaped = ~is_escaped;
else
break; end; end;
if ~is_escaped
indices = [indices i]; end; end; end; end;
function node = deserialize(string)
controls = control_chars(string);
if numel(controls) == 0
node.val = unescape_chars(string);
node.left = [];
node.right = [];
else
if string(controls(1)) ~= '('
error('Invalid control character at %d', controls(1)); end;
nested_level = 0;
top_controls = NaN(3, 1);
for i = controls
switch string(i)
case '('
if nested_level == 0
top_controls(1) = i; end;
nested_level++;
case ','
if nested_level == 1
if ~isnan(top_controls(2))
error('Encountered '','' at %d after finding two children', i); end;
top_controls(2) = i; end;
case ')'
if nested_level <= 1
if isnan(top_controls(2))
error('Encountered '')'' at %d before finding two children', i);
elseif i ~= numel(string)
error('Encountered final '')'' at %d before end of string', i); end;
top_controls(3) = i; end;
nested_level--; end; end;
if any(isnan(top_controls))
error('Incomplete tree description'); end;
node.val = unescape_chars(string(1:(top_controls(1) - 1)));
node.left = deserialize(string((top_controls(1) + 1):(top_controls(2) - 1)));
node.right = deserialize(string((top_controls(2) + 1):(end - 1))); end; end;
