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
|
|