[phone] serialize/de-serialize a tree

Posted by: lexigrey on: August 24, 2013

• In: 面经
• Leave a Comment

这个题和前几天做的另一道“找二叉树的第n个元素“一样，用到的是pass-count technique：用一个IntWrapper keep track of 线性的index。无论tree怎么走，这个index是不断增加的。

serialize很简单，用#表示null，然后中左右(pre order)的traverse一遍就变成serialize的文件了。

deserialize的话，和preorder一样，怎么来的就怎么populate回去。是#，说明populate null，就不用往下做了；不是的话，继续做；重点是要keep track of current element in the array，就用到了一个Integer wrapper好能把count的这个值一路传下去。需要特别小心的是，这个count要一直增加，不管当前是不是#！

Node deserialize(char[] arr, IntWrapper i) {
  i.val++;//这个不能放if后面！
  if (arr[i.val] == '#')
    return null;
  Node newNode = new Node(arr[i.val]);
  newNode.left = deserialize(arr, i);
  newNode.right = deserialize(arr, i);
  return newNode;
}

Advertisements

Tags: tree, 前序, 固定解法