检查由未排序数组构造的二叉搜索树的相等性
Checking for equality of binary search trees constructed from unsorted arrays
这里已经有人问过这个问题：
不过，我想到的解决方法比较简单，这里没有提到。
问题陈述是：Given two arrays which represent a sequence of keys. Imagine we make a Binary Search Tree (BST) from each array. We need to tell whether two BSTs will be identical or not without actually constructing the tree.
我想到的是，只需对两个数组进行排序即可。如果它们相同，那么它们的中序遍历也将相同，因此如果两个数组相同，那么它们肯定会导致相同的 BST。我假设如果两个二叉搜索树的中序遍历相同，那么树也会相同，我错了吗？
仅中序遍历不能定义唯一的BST。你必须得到另一个 pre/post 顺序遍历来重建 BST。
除非我误解了你所说的 "inorder traversal" 的意思，否则这是行不通的。不仅 BST 的中序遍历不唯一，事实上 every BST 在同一组元素上的中序遍历是相同的。这是一个小例子：
4
/\
2/ \
/\ \
1 3 5
2
/\
/
/ /\
1 3 5
两棵树的中序遍历为 1、2、3、4、5。因此即使树不同，您的方法也会报告 "IDENTICAL"。
你的做法实际上在另一个方向上也是错误的。如果两个 BST 具有相同的结构但元素不同，那么您应该报告 "IDENTICAL"，但当然它们的排序列表（= 中序遍历）是不同的——因此在这种情况下您将报告 "DIFFERENT"。
这里已经有人问过这个问题： 不过，我想到的解决方法比较简单，这里没有提到。 问题陈述是： 我想到的是，只需对两个数组进行排序即可。如果它们相同，那么它们的中序遍历也将相同，因此如果两个数组相同，那么它们肯定会导致相同的 BST。我假设如果两个二叉搜索树的中序遍历相同，那么树也会相同，我错了吗？
Given two arrays which represent a sequence of keys. Imagine we make a Binary Search Tree (BST) from each array. We need to tell whether two BSTs will be identical or not without actually constructing the tree.
仅中序遍历不能定义唯一的BST。你必须得到另一个 pre/post 顺序遍历来重建 BST。
除非我误解了你所说的 "inorder traversal" 的意思，否则这是行不通的。不仅 BST 的中序遍历不唯一，事实上 every BST 在同一组元素上的中序遍历是相同的。这是一个小例子：
4
/\
2/ \
/\ \
1 3 5
2
/\
/
/ /\
1 3 5
两棵树的中序遍历为 1、2、3、4、5。因此即使树不同，您的方法也会报告 "IDENTICAL"。
你的做法实际上在另一个方向上也是错误的。如果两个 BST 具有相同的结构但元素不同，那么您应该报告 "IDENTICAL"，但当然它们的排序列表（= 中序遍历）是不同的——因此在这种情况下您将报告 "DIFFERENT"。