/*题目描述
- Given a binary tree, determine if it is a valid binary search tree (BST).
- Assume a BST is defined as follows:
- The left subtree of a node contains only nodes with keys less than the node's key.
- The right subtree of a node contains only nodes with keys greater than the node's key.
- Both the left and right subtrees must also be binary search trees.
- Input array is described as val(left,right).
- etc:
- input:
- 67(,7(,16(,)))
- output:
- 0 / /思路
- 1: 找到字符串中所有左括号的坐标，建立数组
- 2：找到每个左括号对应的逗号的坐标，并建立数组。 左括号数组i号位对应逗号i号位
- 3：比较每一个 括号左位 < 括号右位 < 逗号左位 */ #include using namespace std;
//struct 树
struct Tree{
string treeStr;
int* pare;
int* comma;
};
Tree* init(int*, int*);
bool isBST(Tree*);
void getPare(string, int*);
void getComma(string, int*, int*);
int main() {
int* pare;
int* comma;
Tree* tree = init(pare, comma);
bool isBst = isBST(tree);
cout << isBst;
delete[] pare;
delete[] comma;
delete[] tree;
return 0;
}
//找到左括号对应的逗号
Tree* init(int* pare, int* comma){
string str;
cout << "input your tree: ";
getline(cin,str);
getPare(str,pare);
getComma(str, pare, comma);
Tree theTree = {str, pare, comma};
cout << theTree.comma;
cout << theTree.pare;
delete[] pare;
delete[] comma;
return &theTree;
}
bool isBST(Tree* tree){
return false;
}
void getPare(string str, int* pare){
/*
* 待完善的。
* 1、有没有更好的办法 使得不用重复两次while语句
*/
int i=0;
int position = 0;
//确定动态数组的长度，即这个字符串中有多少个 左括号
for(int m=0; m<str.length(); m++){
if(str[m] == '('){
i++;}
}
pare = new int[i];
//赋值到数组中
position = 0;
int k = 0;
while((position = str.find('(',position)) != string::npos){
pare[k] = position;
k++;
}
}
void getComma(string str, int* pare, int* comma){
//为什么 pare.length 不能用 ??? 黑人问号问号??? 是什么原理哇??? 郑涛大哥求讲解！
//这个地方的pare[] 和 pare* 有什么区别吗？？
int i = 0;
for(int m=0; m<str.length(); m++){
if(str[m] == '('){
i++;}
}
comma = new int[i];
for(int k = 0; k<i; k++){
int position = pare[k];
int count = 1;
for(int j = position; j<i; j++){
if(str[j] == '('){
count++;}
if(str[j] == ','){
count--;}
if(count == 0){
comma[k] = j;
break;
}
}
}
}
就是这么一段代码，但是总是不对。 debug模式下连输入string都不成功。。。
