首页 > 代码库 > Sicily:计算二叉查找树的高度
Sicily:计算二叉查找树的高度
Description
给定一个二叉查找树，要求计算其高度，每个二叉查找树将给出先序与中序的遍历。
例如：一个二叉查找树其先序遍历为：16, 10, 4, 15, 23 ; 中序遍历为 4, 10, 15, 16, 23，则其高度为2（假定空树高度为-1，只有根节点的数高度为0）
Input
The first line is the number of test cases. For each test case, the first line is the preorder of keys, the second line is the inorder of the keys.
第一行输入测试用例个数。
对于每个测试用例，第一行是key值的先序遍历，第二行是key值的中序遍历
Output
对于每个测试用例，用一行输出树的高度
Sample Input
Copy sample input to clipboard2 4 5 6 4 5 6 6 4 8 9 10 4 6 8 9 10
Sample Output
2 3
#include <iostream>
#include <vector>
#include <sstream>
using namespace std;
struct TreeNode{
int data;
TreeNode* left;
TreeNode* right;
TreeNode(char data):data(data),left(NULL),right(NULL){
}
};
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
if(preorder.empty()) return NULL;
TreeNode* root = new TreeNode(preorder[0]);
int pos = 0;
while(inorder[pos] != preorder[0]) pos++;
vector<int> left_pre(preorder.begin()+1, preorder.begin()+pos+1);
vector<int> right_pre(preorder.begin()+pos+1, preorder.end());
vector<int> left_in(inorder.begin(), inorder.begin()+pos);
vector<int> right_in(inorder.begin()+pos+1,inorder.end());
root->left = buildTree(left_pre, left_in);
root->right = buildTree(right_pre, right_in);
return root;
}
int h(TreeNode* root) {
if(!root) return -1;
return max(h(root->left), h(root->right)) + 1;
}
void extract(vector<int>& v, string& s) {
stringstream ss(s);
int data;
while(ss >> data) v.push_back(data);
}
int main() {
int numTest;
cin >> numTest;
cin.get();
while(numTest--) {
vector<int> preorder;
vector<int> inorder;
string pre, in;
getline(cin, pre);
getline(cin, in);
extract(preorder,pre);
extract(inorder,in);
TreeNode* root = NULL;
root = buildTree(preorder, inorder);
cout << h(root) << endl;
}
return 0;
}
Sicily:计算二叉查找树的高度
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。