面试题手撕代码系列

手撕代码

二叉搜索树（BST）的建立、插入、遍历

本人第一次面试遇到的，没复习到，没能做出来。

今天复盘，查资料，手撕如下：

#include<iostream>
using namespace std;
#include<vector>
class TreeNode   //define nodes
{
public:
	TreeNode(int in_val):val(in_val),left(nullptr),right(nullptr){}
	void SetVal(int in_val)
	{
		this->val = in_val;
	}
	int GetVal()
	{
		return this->val;
	}
	int val;
	TreeNode* left;
	TreeNode* right;
};

void Tree_insert(TreeNode* root, int val)  //define methods of insert value for the binary tree
{
	if (root->GetVal() == val)
	{
		cout << "more than 1 val equal to" << val << endl;
		return;
	}
	if (root->GetVal() > val && root->left != nullptr)
	{
		Tree_insert(root->left, val);
	}
	else if (root->GetVal() > val && root->left == nullptr)
	{
		TreeNode* new_node = new TreeNode(val);
		root->left = new_node;
		return;
	}
	else if (root->val < val && root->right != nullptr)
	{
		Tree_insert(root->right, val);
	}
	else if (root->val < val && root->right == nullptr)
	{
		TreeNode* new_node = new TreeNode(val);
		root->right = new_node;
		return;
	}
}

TreeNode* build_tree(vector<int>& num)  //make use of the function 'Tree_insert' in order to build the tree
{
	if (num.size() == 0)
	{
		return nullptr;
	}
	TreeNode* root = new TreeNode(num[0]);
	if (num.size() != 1)
	{
		for (int i = 1; i < num.size(); i++)
		{
			Tree_insert(root, num[i]);
		}
	}
	return root;
}

void mid_print(TreeNode* root) // make the InOrderTraversel to verify 
{
	if (root->left != nullptr)
	{
		mid_print(root->left);
	}
	cout << root->val << " ";
	if (root->right != nullptr)
	{
		mid_print(root->right);
	}
}

int main()
{
	vector<int> num = { 10,128,23,15,47,234,65,78,1,2 }; //test
	TreeNode* root = build_tree(num);
	mid_print(root);
	// cout : 1 2 10 15 23 47 65 78 128 234
	// it works.
	return 0;
}

• 先写插入函数，再写建立二叉树的函数，直接用插入的方法建立；
• 中序遍历为严格递增，则为正确代码；
• 关于查找函数，感觉很简单，时间复杂度应该是O(n) = (logn);

快速排序

#include<iostream>
using namespace std;

int partition(int* num, int low, int high)
{
	int p = num[low];
	while (low < high)
	{
		while (low < high && num[high] >= p)
		{
			high--;
		}
		num[low] = num[high];
		while (low < high && num[low] <= p)
		{
			low++;
		}
		num[high] = num[low];
	}
	num[low] = p;
	return low;
}

void quick_sort(int* num, int low, int high)
{
	int p = partition(num, low, high);
	if (low < high)
	{
		quick_sort(num, low, p - 1);
		quick_sort(num, p + 1, high);
	}
}

int main()
{
	int a[10] = { 10,8,12,4,15,4,16,22,34,12 };
	quick_sort(a, 0, 9);
	for (int i = 0; i <= 9; i++)
	{
		cout << a[i] << " ";
	}
	return 0;
}