【树】构建二叉搜索树

本文最后更新于:2021年4月29日 晚上

LeetCode 938.二叉搜索树的范围和

思路

递归就完事了

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
* 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) {}
* };
*/
class Solution {
public:
int rangeSumBST(TreeNode* root, int low, int high) {
if(!root) return 0;
if(root->val > high) return rangeSumBST(root->left, low, high);
if(root->val < low) return rangeSumBST(root->right, low, high);
return root->val+rangeSumBST(root->left, low, high)+rangeSumBST(root->right, low, high);
}
};


AcWing 1589. 构建二叉搜索树

思路

先将所有节点(包括新加入的)排序后再按照层序遍历输出就可以得解
有两种写法,一种是把树/队列用数组模拟出来即可,另外一种是把真正的树结构和队列结构都用起来

C++代码1(模拟树+模拟队列法)

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
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N=110;

int n;
int w[N], l[N], r[N];
int a[N], q[N];

void dfs(int u,int& k)
{
if(u==-1) return;
dfs(l[u], k);
w[u]=a[k++];
dfs(r[u], k);
}

void bfs()
{
int hh=0, tt=0;
q[0]=0;
while(hh<=tt)//队列不空
{
int t=q[hh++];//取出队头
printf("%d ", w[t]);
if(l[t]!=-1)//如果有左儿子
q[++tt]=l[t];
if(r[t]!=-1)//如果有右儿子
q[++tt]=r[t];
}
}

int main()
{
scanf("%d", &n);
for(int i=0;i<n;i++)
scanf("%d%d", &l[i], &r[i]);
for(int i=0;i<n;i++)
scanf("%d", &a[i]);
sort(a, a+n);

int k=0;
dfs(0, k);
bfs();

return 0;
}

C++代码2(树+队列法)

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
#include<bits/stdc++.h>
using namespace std;
struct TreeNode{ //建立数据结构
int val;
int left;
int right;
}root[110]; //节点数组
int n,co;
int num[110];
vector<int> ans;
void dfs(int u) //中序遍历把值赋给root[].val
{
if(u==-1) return ;

dfs(root[u].left);
root[u].val=num[co++];
dfs(root[u].right);
}
void bfs() //层序遍历存储答案输出的值的顺序
{
queue<TreeNode> q;
q.push(root[0]);

while(q.size())
{
auto t = q.front();
q.pop();

ans.push_back(t.val);
if(t.left!=-1) q.push(root[t.left]);
if(t.right!=-1) q.push(root[t.right]);
}
}
int main()
{
cin>>n;
int l,r;
for(int i=0;i<n;i++)
{
cin>>l>>r;
root[i].left=l;
root[i].right=r;
}

for(int i=0;i<n;i++) cin>>num[i];

sort(num,num+n); //将输入的数组元素从小到大排列,用来匹配二叉搜索树的赋值情况
dfs(0);
bfs();

int f=0;
for(auto x:ans)
{
if(f) cout<<" ";
cout<<x;
f=1;
}
return 0;
}