[phone] serialize/de-serialize a tree
Posted August 24, 2013
on:- 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;
}
Leave a Reply