題目描述

對(duì)于一個(gè)元素各不相同且按升序排列的有序序列，請(qǐng)編寫一個(gè)算法，創(chuàng)建一棵高度最小的二叉查找樹。

給定一個(gè)有序序列int[] vals,請(qǐng)返回創(chuàng)建的二叉查找樹的高度。

/*struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode(int data) : val(data),left(NULL),right(NULL) {} };*/class MinimalBST { public:int getHeight(TreeNode *root){if(!root)return 0;int hleft = getHeight(root->left);int hright = getHeight(root->right);return hleft > hright ? (hleft+1) : (hright+1);}TreeNode *build(vector<int> vals,int left,int right){if(left > right)return NULL;int middle = left + (right-left)/2;TreeNode *root = new TreeNode(vals[middle]);root->left = build(vals,left,middle-1);root->right = build(vals,middle+1,right);return root;}int buildMinimalBST(vector<int> vals) {if(vals.size() == 0)return 0;TreeNode * root = build(vals,0,vals.size()-1);return getHeight(root);} };

?

轉(zhuǎn)載于:https://www.cnblogs.com/xiuxiu55/p/6735848.html

總結(jié)

以上是生活随笔為你收集整理的高度最小的BST的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。