在构造二叉树时处理重复项

Question

我在leetcode - https://leetcode.com/problems/serialize-and-deserialize-binary-tree/遇到了以下问题

我能够在下面编写一个算法(找到预顺序和后顺序遍历并保存它们)。然后从遍历中重建树)，但已经达到了一个更基本的问题-即。如何构造具有重复值的二叉树?我失败的测试用例是[3,2,4,3]，其中前置顺序和后置顺序是相同的。

任何帮助和建议都是感激的。

public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if(root == null) return null;
ArrayList<Integer> inorder = inOrder(root, new ArrayList<Integer>());
ArrayList<Integer> preorder = preOrder(root, new ArrayList<Integer>());
StringBuilder sb = new StringBuilder("");
for(int val : inorder){
sb.append(val + " ");
}
sb.append("|");
for(int val : preorder){
sb.append(val + " ");
}
String serialized = sb.toString();
return serialized;
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if(data == null)return null;
String[]result = data.split("\|");
String[] inString = result[0].split(" ");
String[] preString = result[1].split(" ");
int i = 0;
int[] inorder = new int[inString.length];
int[] preorder = new int[preString.length];
for(i = 0; i < inString.length; i++){
inorder[i]= Integer.parseInt(inString[i]);
}
for(i = 0; i < preString.length; i++){
preorder[i]= Integer.parseInt(preString[i]);
}
return buildTree(preorder, inorder);
}
/*
Inorder Tree Traversal
*/
private ArrayList<Integer> inOrder(TreeNode root, ArrayList<Integer> inorder){
if(root == null ){
return inorder;
}
inorder = inOrder(root.left, inorder);
inorder.add(root.val);
inorder = inOrder(root.right, inorder);

return inorder;
}
/*
Pre-order Tree Traversal
*/
private ArrayList<Integer> preOrder(TreeNode root, ArrayList<Integer> preorder){
if(root == null ){
return preorder;
}
preorder.add(root.val);
preorder = preOrder(root.left, preorder);
preorder = preOrder(root.right, preorder);

return preorder;
}

public TreeNode buildTree(int[] preorder, int[] inorder) {
return buildTreeHelper(inorder, 0, inorder.length - 1, preorder, 0, preorder.length-1);
}
public TreeNode buildTreeHelper(int[] in, int ins, int ine, int[] pre, int pres, int pree){
if(pree < pres || ine < ins) return null;

TreeNode root = new TreeNode(pre[pres]);
int index = 0;
for(int i = ins; i <= ine; i++){
if(in[i] == root.val){
index = i;
break;
}
}
root.left = buildTreeHelper(in, ins, index - 1,  pre, pres + 1,  pres + index - ins + 1);
root.right = buildTreeHelper(in, index + 1, ine, pre, pres + (index - ins) + 1, pree);

return root;
}
}

感谢

Answer 1

您的序列化——基于有序和预有序表示——确实依赖于树中值的唯一性。以以下序列化为例:

inorder  | preorder
1 1 2 1 2|1 1 1 2 2

这些不是定义单个二叉树。例如，下面两个树都有遍历顺序:

1                 1
/                / 
1   2             1   1
/                    / 
1   2                 2   2

所以你需要想出另一个序列化的想法。