【树】构建二叉搜索树

title: 【树】构建二叉搜索树
tags:

• 每日一题
• leetcode
• acwing
• 树
  abbrlink: 9e5e150
  date: 2021-04-29 18:25:53

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

思路

递归就完事了

C++代码

/**
 * 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(模拟树+模拟队列法)

#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（树+队列法）

#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;
}