面试手撕—二叉搜索树及其后序遍历

一、引言

在面试地平线的时候，聊到了二叉搜索树，让手撕二叉搜索树，以下是要求

1、用类模板实现二叉搜索树

2、写一个函数，实现给一个vector数组，转换成二叉搜索树

3、写出二叉搜索树的后序遍历

 

二、代码实现

#include <iostream>
#include <vector>using 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 TreeNode<T>(val);} else {insert(root, val);}}bool find(T val) {return find(root, val);}void postorderTraversal() {postorderTraversal(root);std::cout << std::endl;}private:TreeNode<T>* root;void insert(TreeNode<T>* node, T val) {if (val < node->val) {if (node->left == NULL) {node->left = new TreeNode<T>(val);} else {insert(node->left, val);}} else {if (node->right == NULL) {node->right = new TreeNode<T>(val);} else {insert(node->right, val);}}}bool find(TreeNode<T>* 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(TreeNode<T>* node) {if (node == NULL) {return;}postorderTraversal(node->left);postorderTraversal(node->right);std::cout << node->val << " ";}
};int main() {vector<int> arr = {5, 3, 7, 2, 4, 6, 8};BST<int> 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(vector<int>& nums) 
{return build(nums, 0, nums.size() - 1);
}TreeNode* build(vector<int>& 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;
}