h*****g
发帖数: 312 | 1 Check if identical BSTs from given number streams
Question: You are given 2 number streams. You need to find whether they will
create the same BST or not.
Example:
Array1:10 5 20 15 30
Array2:10 20 15 30 5
Result: True
Array1:10 5 20 15 30
Array2:10 15 30 20 5
Result: False | P*******U
发帖数: 203 | 2 对每一个stream（以数组形式），切分为第一个元素（root),比root小的元素数组（
left)以及比root大的元素数组(right),并统计stream的元素总数。
如果元素总数不同或者root不同，直接返回false。
否则，递归的用这个过程比较两个stream的left数组和right数组，如果都相同，返回
true，否则，返回false | P***o
发帖数: 96 | 3 第一个能解释一下为什么是true么？
array2的5在10的右边为什么是bst?
谢谢
will
【在 h*****g 的大作中提到】
: Check if identical BSTs from given number streams
: Question: You are given 2 number streams. You need to find whether they will
: create the same BST or not.
: Example:
: Array1:10 5 20 15 30
: Array2:10 20 15 30 5
: Result: True
: Array1:10 5 20 15 30
: Array2:10 15 30 20 5
: Result: False
| w****o
发帖数: 2260 | 4 能不能解释一下这个题给定的条件和要解决的问题？好像很模糊的。
number steam是按照BST的什么order遍历的结果，还是随意的？
为什么第一个例子返回的结果是true? 而第二个例子的结果是false? 我看不出有什么
不同。
还有number steam里面可以有重复的数字吗？
我记得BST的左子树的数字 <= 当前的节点 < 右子树，对吧？
will
【在 h*****g 的大作中提到】
: Check if identical BSTs from given number streams
: Question: You are given 2 number streams. You need to find whether they will
: create the same BST or not.
: Example:
: Array1:10 5 20 15 30
: Array2:10 20 15 30 5
: Result: True
: Array1:10 5 20 15 30
: Array2:10 15 30 20 5
: Result: False
| P*******U
发帖数: 203 | 5 lz的意思是按给定的stream的顺序插入一个空的BST | p*****2
发帖数: 21240 | 6
这个应该可以。我也是这个思路。
【在 P*******U 的大作中提到】
: 对每一个stream（以数组形式），切分为第一个元素（root),比root小的元素数组（
: left)以及比root大的元素数组(right),并统计stream的元素总数。
: 如果元素总数不同或者root不同，直接返回false。
: 否则，递归的用这个过程比较两个stream的left数组和right数组，如果都相同，返回
: true，否则，返回false
| h*****g
发帖数: 312 | 7 按给定的stream的顺序插入一个空的BST
【在 w****o 的大作中提到】
: 能不能解释一下这个题给定的条件和要解决的问题？好像很模糊的。
: number steam是按照BST的什么order遍历的结果，还是随意的？
: 为什么第一个例子返回的结果是true? 而第二个例子的结果是false? 我看不出有什么
: 不同。
: 还有number steam里面可以有重复的数字吗？
: 我记得BST的左子树的数字 <= 当前的节点 < 右子树，对吧？
:
: will
| h*****g
发帖数: 312 | 8 按给定的stream的顺序插入一个空的BST
【在 P***o 的大作中提到】
: 第一个能解释一下为什么是true么？
: array2的5在10的右边为什么是bst?
: 谢谢
:
: will
| b******i
发帖数: 914 | 9 弱弱问一下，这个你在切分的时候，是不是按照quicksort里面的partition那样？
如果是的话，岂不是会打乱原来的顺序（因为partition是不稳定的）？
【在 P*******U 的大作中提到】
: 对每一个stream（以数组形式），切分为第一个元素（root),比root小的元素数组（
: left)以及比root大的元素数组(right),并统计stream的元素总数。
: 如果元素总数不同或者root不同，直接返回false。
: 否则，递归的用这个过程比较两个stream的left数组和right数组，如果都相同，返回
: true，否则，返回false
| A**u
发帖数: 2458 | 10 #include
using namespace std;
bool is_same_bst(int* A, int m, int* B, int n)
{
if ( m == 0 & n == 0 )
return true;
if ( m != n)
return false;
else
{
if ( A[0] != B[0] ) // root
return false;
else
{
//看看，root,左右儿子数目是否一致
int smaller1 = 0;
int larger1 = 0;
for(int i = 1; i < m; ++i)
{
if ( A[i] < A[0] ) ++smaller1;
if ( A[i] > A[0] ) ++larger1;
}
int smaller2 = 0;
int larger2 = 0;
for(int i = 1; i < n; ++i)
{
if ( B[i] < B[0] ) ++smaller2;
if ( B[i] > B[0] ) ++larger2;
}
//递归
if (smaller1 != smaller2 || larger1 != larger2 )
return false;
else
{
int* A_left=0;
if (smaller1 > 0) A_left = new int[smaller1];
int* B_left=0;
if (smaller2 > 0) B_left = new int[smaller2];
int* A_right=0;
if (larger1 > 0 ) A_right = new int[larger1];
int* B_right=0;
if (larger1 > 0 ) B_right = new int[larger1];
int i = -1;
int j = -1; //创建左右子序列
for(int k = 1; k < m; ++k)
{
if (A[k] < A[0])
{
++i;
A_left[i] = A[k];
}
if ( A[k] > A[0])
{
++j;
A_right[j] = A[k];
}
}
i = -1;
j = -1; //数组B
for(int k = 1; k < n; ++k)
{
if (B[k] < B[0])
{
++i;
B_left[i] = B[k];
}
if ( B[k] > B[0])
{
++j;
B_right[j] = B[k];
}
}
bool result = is_same_bst(A_left,smaller1,B_left,smaller2) &&
is_same_bst(A_right,larger1,B_right,larger2);
if (larger1 > 0) delete []A_right;
if (larger2 > 0) delete []B_right;
if (smaller1 > 0) delete []A_left;
if (smaller2 > 0) delete []B_left;
return result;
}
}
}
}
int main(){
int A[5] = {10,5,20,15,30};
int B[5] = {10,20,15,30,5};
int C[5] = {10,15,30,20,5};
cout << is_same_bst(A,5,B,5) << endl;
cout << is_same_bst(A,5,C,5) << endl;
return 0;
}
参考算法 http://tech-queries.blogspot.com/2011/06/check-if-identical-bsts-from-given.html | F********u
发帖数: 7 | 11 bool is_same_BST(int *A, int m, int a_min, int a_max, int *B, int n, int b_
min, int b_max)
{
if( A == NULL || B == NULL )
return false;
if( m == 0 && n == 0 )
return true;
if( m == 0 || n == 0 )
return false;
if( A[0] != B[0] )
return false;
int i, j, a, b;
// A tree -> left subtree root
for( i = 1; i < m; i++ )
{
if( A[i] > a_min && A[i] < A[0] )
break;
}
// B tree -> left subtree root
for( j = 1; j < n; j++ )
{
if( B[j] < B[0] && B[j] > b_min )
break;
}
// A tree -> right subtree root
for( a = 1; a < m; a++ )
{
if( A[a] > A[0] && A[a] < a_max )
break;
}
// B tree -> right subtree root
for( b = 1; b < n; b++ )
{
if( B[b] > B[0] && B[b] < b_max )
break;
}
return is_same_BST( &A[i], m-i, a_min, A[0], &B[j], n-j, b_min, B[0] )
&& is_same_BST( &A[a], m-a, A[0], a_max, &B[b], n-b, B[0], b_max
) ;
}
int main()
{
int A[5] = {10,5,20,15,30};
int B[5] = {10,20,15,30,5};
int C[5] = {10,15,30,20,5};
cout << is_same_BST(A,5,INT_MIN, INT_MAX,B,5,INT_MIN, INT_MAX) << endl;
cout << is_same_BST(A,5,INT_MIN, INT_MAX,C,5,INT_MIN, INT_MAX) << endl;
} | s********r
发帖数: 137 | 12 /**
* Took FightingXu's algorithm and implemented in JAVA:
*/
public static boolean isSameBST(int[] arrA, int aOffset, int aMin, int aMax,
int[] arrB, int bOffset, int bMin, int bMax)
{
if (arrA == null || arrB == null)
return false;
if (aOffset > -1 && aOffset == 0 && bOffset > -1 && bOffset == 0)
return true;
if (arrA.length == aOffset || arrB.length == bOffset)
return false;
if (aOffset > -1 && bOffset > -1 && arrA[aOffset] != arrB[bOffset])
return false;
int i, aLeftOffset = 0, bLeftOffset = 0, aRightOffset = 0, bRightOffset = 0;
aOffset = aOffset < 0 ? 0 : aOffset;
bOffset = bOffset < 0 ? 0 : bOffset;
// A tree -> left subtree root
for (i = aOffset + 1; i < arrA.length; i++)
{
if (arrA[i] > aMin && arrA[i] < arrA[aOffset])
{
aLeftOffset = i;
break;
}
}
// B tree -> left subtree root
for (i = bOffset + 1; i < arrB.length; i++)
{
if (arrB[i] > bMin && arrB[i] < arrB[bOffset])
{
bLeftOffset = i;
break;
}
}
// A tree -> right subtree root
for (i = aOffset + 1; i < arrA.length; i++)
{
if (arrA[i] > arrA[aOffset] && arrA[i] < aMax)
{
aRightOffset = i;
break;
}
}
// B tree -> right subtree root
for (i = bOffset + 1; i < arrB.length; i++)
{
if (arrB[i] > arrB[bOffset] && arrB[i] < bMax)
{
bRightOffset = i;
break;
}
}
return isSameBST(arrA, aLeftOffset, aMin, arrA[aLeftOffset], arrB, bLeftOffset, bMin, arrB[bLeftOffset])
&& isSameBST(arrA, aRightOffset, arrA[aRightOffset], aMax, arrB, bRightOffset, arrB[bRightOffset], bMax);
}
public static void main(String[] args) {
int[] arrA = {10,5,20,15,30};
int[] arrB = {10,20,15,30,5};
int[] arrC = {10,15,30,20,5};
boolean sameBST = BinaryTree.isSameBST(arrA, -1, Integer.MIN_VALUE, Integer.MAX_VALUE,
arrB, -1, Integer.MIN_VALUE, Integer.MAX_VALUE);
System.out.println(sameBST);
sameBST = BinaryTree.isSameBST(arrA, -1, Integer.MIN_VALUE, Integer.MAX_VALUE,
arrC, -1, Integer.MIN_VALUE, Integer.MAX_VALUE);
System.out.println(sameBST);
} | s*******f
发帖数: 1114 | 13 python:
def SameBST(a, b):
if len(a) < 1:
return len(b) < 1;
if len(a) != len(b) or a[0] != b[0]:
return False
aleft = [x for x in a if x < a[0]]
aright = [x for x in a if x > a[0]]
bleft = [x for x in b if x < b[0]]
bright = [x for x in b if x > b[0]]
return SameBST(aleft, bleft) and SameBST(aright, bright)
if __name__ == "__main__":
a = [10, 5, 20, 15, 30]
b = [10, 20, 15, 30, 5]
b1 = SameBST(a, b)
c = [10, 5, 20, 15, 30]
d = [10, 15, 20, 30, 5]
b2 = SameBST(c, d)
pass
will
【在 h*****g 的大作中提到】
: Check if identical BSTs from given number streams
: Question: You are given 2 number streams. You need to find whether they will
: create the same BST or not.
: Example:
: Array1:10 5 20 15 30
: Array2:10 20 15 30 5
: Result: True
: Array1:10 5 20 15 30
: Array2:10 15 30 20 5
: Result: False
|
|
