面试题手撕代码系列

本文最后更新于:2024年7月31日 下午

手撕代码

二叉搜索树(BST)的建立、插入、遍历

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

今天复盘,查资料,手撕如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#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);

快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#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;
}

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!