树的习题(From PAT甲级 & LeetCode

PAT甲级

二叉树的遍历

• 1086. Tree Traversals Again
• 1102. Invert a Binary Tree

树的遍历

• 1079. Total Sales of Supply Chain
• 1090. Highest Price in Supply Chain
• 1094. The Largest Generation
• 1004. Counting Leaves
• 1053. Path of Equal Weight (30)

BST

• 1043. Is It a Binary Search Tree
• 1064. Complete Binary Search Tree
• 1099. Build A Binary Search Tree

AVL
1066. Root of AVL Tree

/*1043.先根据序列构造出BST or mirror BST，然后再比较先序遍历序列是否相等，然后再输出后序遍历的序列*/
#include<iostream>
#include<vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) :val(x), left(NULL), right(NULL) {};
};


void insert(TreeNode* &root,int x)
{
    if (root == NULL) {
        root = new TreeNode(x);
        return;
    }
    if (x < root->val) {
        insert(root->left, x);
    }
    if (x >= root->val) {
        insert(root->right, x);
    }
}

void mirrorinsert(TreeNode* &root, int x)
{
    if (root == NULL) {
        TreeNode* node = new TreeNode(x);
        root = node;
        return;
    }
    if (x >= root->val) {
        mirrorinsert(root->left, x);
    }
    if (x < root->val) {
        mirrorinsert(root->right, x);
    }
}
TreeNode* buildTree(vector<int> &input)
{
    int Size = input.size();
    TreeNode* root = new TreeNode(input[0]);
    if (Size == 1)
        return root;
    bool flag = true;
    if (input[1] > input[0]) {
        flag = false;//mirror bst
    }
    if (flag)//insert
    {
        for (int i = 1; i < Size; i++)
        {
            insert(root, input[i]);
        }
    }
    else
    {
        for (int i = 1; i < Size; i++) {
            mirrorinsert(root, input[i]);
        }

    }
    return root;

}
vector<int> preorder(TreeNode* root)
{
    TreeNode* cur = root;
    vector<int> preOrder,tmp1,tmp2;
    preOrder.push_back(cur->val);
    if (root->left) {
        tmp1 = preorder(root->left);
        preOrder.insert(preOrder.end(), tmp1.begin(), tmp1.end());
    }
    if (root->right) {
        tmp2 = preorder(root->right);
        preOrder.insert(preOrder.end(), tmp2.begin(), tmp2.end());
    }
    return preOrder;
}
vector<int> postorder(TreeNode* root)
{
    TreeNode* cur = root;
    vector<int> postOrder, tmp1, tmp2;
    if (!root)
        return postOrder;
    tmp1 = postorder(root->left);
    postOrder.insert(postOrder.end(), tmp1.begin(), tmp1.end());
    tmp2 = postorder(root->right);
    postOrder.insert(postOrder.end(), tmp2.begin(), tmp2.end());
    postOrder.push_back(cur->val);
    return postOrder;
}
int main()
{
    
    int  m;//树的结点数
    cin >> m;
    vector<int> input(m);
    for (int i = 0; i < m; i++) {
        cin>>input[i];
    }
    TreeNode* tree = buildTree(input);
    bool judge = true;
    vector<int> pre = preorder(tree);
    for (int i = 0; i < m; i++) {
        if (pre[i] != input[i]) {
            judge = false;
            break;
        }
    }
    if (judge) {
        cout << "Yes" << endl;
        vector<int> post = postorder(tree);
        for (int i = 0; i < m-1; i++) {
            cout << post[i] << " ";
        }
        cout << post[m - 1];
    }
    else {
        cout << "No" << endl;
    }
    
    return 0;
}

/*1064:给定一组序列，构造完全二叉搜索树，输出层序遍历序列*/
/*思路：完全二叉树用数组来表示，中序遍历这个数组，按遍历的顺序把数字从小到大赋值即构造出完全二叉搜索树
比如，第一次访问下标为7的数组a节点，则赋值a[7] = min*/
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;
int i=0;//表示排好序的数组下标

void buildCBST(vector<int> &cbst,vector<int> &input,int index) {//递归
    if (index >= input.size()) {
        return;
    }
    buildCBST(cbst, input, index * 2 + 1);//左子树
    cbst[index] = input[i++];
    buildCBST(cbst,input,index*2+2);//右子树
}
int main()
{
    int n;
    cin >> n;
    vector<int> input(n),cbst(n);
    for (int j = 0; j < n; j++) {
        cin >> input[j];
    }

    sort(input.begin(), input.end());
    /*for (int j = 0; j < n; j++) {
        cout << input[j]<<" ";
    }*/
    buildCBST(cbst, input, 0);
    for (int j = 0; j < cbst.size()-1; j++) {
        cout<< cbst[j]<<" ";
    }
    cout << cbst[n - 1];
    return 0;
}

/*1107. Social Clusters */
#pragma warning(disable:4996)
#include<cstdio>
#include<algorithm>
const int N = 1001;
using namespace std;
int id[N] = { 0 };
int course[N] = { 0 };
int isroot[N] = { 0 };

void init(int n) {
    for (int i = 1; i <=n; i++) {
        id[i] = i;
        isroot[i] = 0;
    }
}
int root(int x) {
    if (x == id[x])return x;
    else {
        int r = root(id[x]);
        id[x] = r;
        return r;
    }
}
bool find(int p, int q) {
    return root(p) == root(q);
}

void unit(int q, int p) {
    if (!find(q, p)) {//p,q不在一个集合里,把q集合加入p集合
        id[root(q)] = id[root(p)];//q集合根节点指向p集合根节点
    }
}
bool cmp(int a, int b) {
    return a > b;
}
int main() {
    int m,k,h;
    scanf("%d\n", &m);
    init(m);
    for (int i = 1; i <= m; i++) {
        scanf("%d:", &k);
        for (int j = 0; j < k; j++) {
            scanf("%d",&h);
            if (course[h] == 0) {
                course[h] = i;//第一个i选择兴趣h的作为根节点，以后也选择这个兴趣的和根节点加入一个集合
            }
            unit(i, root(course[h]));//实际上是i和root(一样兴趣的人）unit
        }
    }
    for (int i = 1; i <= m; i++) {
        isroot[root(i)]++;//根节点连着几个人
    }
    int sum = 0;//几个集合
    for (int i = 1; i <= m; i++) {
        if (isroot[i] != 0) {
            sum++;
        }
    }
    printf("%d\n",sum);
    sort(isroot+1, isroot + m + 1, cmp);
    for (int i = 1; i <sum; i++) {
        printf("%d ", isroot[i]);
    }
    printf("%d", isroot[sum]);
    return 0;
}