what's the difference between this and #297 ?

@jordandong One is for BT and other is for BST. You are asking because probably your previous encoding scheme for Binary tee is still working successfully for BST too. Same here too, I've just copy pasted #297's code and got accepted. But not everybody's encoding scheme of BT will work for BST too, because they might used different policy, not generic and only suitable for BT.

@kaidul Every BST is a BT, so how would a BT solution fail for BSTs? I think you got it backwards. A solution for BST could fail BT, not the other way around.

@StefanPochmann yes you're correct, thanks for pointing out. I've just thought in opposite direction.

Now that I've actually read and solved this problem: The difference is the bold "The encoded string should be as compact as possible" here. The special property of binary search trees compared to general binary trees allows a more compact encoding. So while the solutions to problem #297 still work here as well, they're not as good as they should be.

@StefanPochmann I was wondering about that. I did also notice that this was specific to BST but I couldn't think how you could take advantage of that requirement to help make the serialization more compact then any regular BT. If you have an idea I'd love to hear it. Thanks!

@三千世界 thanks, I see that now. But still wondering if a given BST solution will really be any better than an optimized BT solution. For example, I've solved it here
for the general BT case and I'm not sure if there is a more compact BST solution. If you have any thoughts please share. Thanks!


@jdrogin
in both kinds of trees, you have to traverse every node once, therefore I dont think BST can do any better than a normal binary tree

@matrixyy said in what's the difference between this and #297 ?:
@StefanPochmann How to do more compact than BT? Could you provide your code? Thank
For Binary tree solution, we need to have "#" or "null" to indicate null node in the serialized string.
However, for BST, we don't need such "#" which make it more compact.

Agree @steven5: There is no need to use "#" or "null" in BST which makes it more compact!
The reason is that we can reconstruct BST by only using preorder(/postorder/levelorder) traversal.
However, in the binary tree situation, we need to use preorder(/postorder/levelorder) + inorder to reconstruct the tree. If we want to directly construct BT, we have to use "#" or "null".Check the full solution here.