放单网站建设,成都企业名录,时尚网站模板代码,惠州注册公司流程和费用一、引言
在面试地平线的时候#xff0c;聊到了二叉搜索树#xff0c;让手撕二叉搜索树#xff0c;以下是要求
1、用类模板实现二叉搜索树
2、写一个函数#xff0c;实现给一个vector数组#xff0c;转换成二叉搜索树
3、写出二叉搜索树的后序遍历 二、代码实现
#inc…一、引言
在面试地平线的时候聊到了二叉搜索树让手撕二叉搜索树以下是要求
1、用类模板实现二叉搜索树
2、写一个函数实现给一个vector数组转换成二叉搜索树
3、写出二叉搜索树的后序遍历 二、代码实现
#include iostream
#include vectorusing namespace std;template typename T
struct TreeNode {T val;TreeNode* left;TreeNode* right;TreeNode(T x) : val(x), left(NULL), right(NULL) {}
};template typename T
class BST {
public:BST() : root(NULL) {}void insert(T val) {if (root NULL) {root new TreeNodeT(val);} else {insert(root, val);}}bool find(T val) {return find(root, val);}void postorderTraversal() {postorderTraversal(root);std::cout std::endl;}private:TreeNodeT* root;void insert(TreeNodeT* node, T val) {if (val node-val) {if (node-left NULL) {node-left new TreeNodeT(val);} else {insert(node-left, val);}} else {if (node-right NULL) {node-right new TreeNodeT(val);} else {insert(node-right, val);}}}bool find(TreeNodeT* node, T val) {if (node NULL) {return false;}if (val node-val) {return true;} else if (val node-val) {return find(node-left, val);} else {return find(node-right, val);}}void postorderTraversal(TreeNodeT* node) {if (node NULL) {return;}postorderTraversal(node-left);postorderTraversal(node-right);std::cout node-val ;}
};int main() {vectorint arr {5, 3, 7, 2, 4, 6, 8};BSTint bst;//可以用以下这种方法将一个vector数组转换成二叉搜索树for (int i 0; i arr.size(); i) {bst.insert(arr[i]);}bst.postorderTraversal(); // 输出2 4 3 6 8 5 7return 0;
} 延伸一个实现实现一个函数就是将一个vector有序数组转换成高度平衡的二叉搜索树 /*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/TreeNode* sortedArrayToBST(vectorint nums)
{return build(nums, 0, nums.size() - 1);
}TreeNode* build(vectorint nums, int l, int r) {if (l r) return nullptr;int mid l r 1;auto root new TreeNode(nums[mid]);root-left build(nums, l, mid - 1);root-right build(nums, mid 1, r);return root;
}
