# 二叉树部分题解

大二上学期，做了一些树的题放一些个人的题解，正在熟悉 C++, 闲来无事时可以翻看。嘿嘿
行高亮
/*******************************************************************************
* 1.相同的树
*/
#include <iostream>
#include <vector>
#include <queue>
#include <sstream>
#include <limits>
#include <cmath>
using namespace std;

//数据结构一：常规二叉树
struct TreeNode1 {
    int val;
    TreeNode1* left;
    TreeNode1* right;
    TreeNode1(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 将数组转换为层序二叉树的函数
TreeNode1* arrayToTree1(const vector<string>& arr) {
    if (arr.empty()) {
        return nullptr;
    }

    // 构建根节点
    TreeNode1* root = new TreeNode1(stoi(arr[0]));
    queue<TreeNode1*> q;
    q.push(root);

    int i = 1;
    while (!q.empty() && i < arr.size()) {
        TreeNode1* current = q.front();
        q.pop();
//stoi是C++中的一个函数，用于将字符串转换为整数。它的完整名称是std::stoi，属于<string>头文件中的函数。
        // 构建左子树节点
        if (arr[i] != "null") {
            current->left = new TreeNode1(stoi(arr[i]));
            q.push(current->left);
        }
        i++;

        // 构建右子树节点
        if (i < arr.size() && arr[i] != "null") {
            current->right = new TreeNode1(stoi(arr[i]));
            q.push(current->right);
        }
        i++;
    }
    return root;
}

// 判断两个二叉树是否相同的函数
bool isSameTree1(TreeNode1* p, TreeNode1* q) {
    if (p == nullptr && q == nullptr) {
        return true;
    }

    if (p == nullptr || q == nullptr) {
        return false;
    }

    return (p->val == q->val) && isSameTree1(p->left, q->left) && isSameTree1(p->right, q->right);
}

// 释放二叉树内存的函数
void deleteTree1(TreeNode1* root) {
    if (root == nullptr) {
        return;
    }

    deleteTree1(root->left);
    deleteTree1(root->right);
    delete root;
}

int main_1() {
    string arrayString1;

    getline(cin, arrayString1);//getline可以读入空格，以换行结束
/*
    // 找到第一个数组部分的起始位置和结束位置
    size_t start1 = input.find('[');
    size_t end1 = input.find(']');

    // 提取第一个数组部分的字符串
    string arrayString1 = input.substr(start1 + 1, end1 - start1 - 1);

    // 找到第二个数组部分的起始位置和结束位置
    size_t start2 = input.find('[', end1 + 1);
    size_t end2 = input.find(']', start2 + 1);

    // 提取第二个数组部分的字符串
    string arrayString2 = input.substr(start2 + 1, end2 - start2 - 1);
*/
    string arrayString2;

    getline(cin, arrayString2);//getline可以读入空格，以换行结束

    // 解析输入字符串为字符串数组1
    vector<string> arr1;
    stringstream ss1(arrayString1);
    string token1;

    while (getline(ss1, token1, ',')) {
        arr1.push_back(token1);
    }
    // 解析输入字符串为字符串数组2
    vector<string> arr2;
    stringstream ss2(arrayString2);
    string token2;

    while (getline(ss2, token2, ',')) {
        arr2.push_back(token2);
    }

    if (arr1.size() != arr2.size()) {
        cout << "false" << endl;
    }
    else {
        // 构建第一个二叉树
        TreeNode1* p = arrayToTree1(arr1);

        // 构建第二个二叉树
        TreeNode1* q = arrayToTree1(arr2);

        // 判断两个二叉树是否相同
        bool result = isSameTree1(p, q);
        cout  << boolalpha << result << endl;

        // 释放二叉树内存
        deleteTree1(p);
        deleteTree1(q);
    }

   
    return 0;
}

/*********************************************************************************
2.二叉树的中序遍历,判断它是不是镜面对称
*/
// 判断二叉树是否对称的辅助函数
bool isSymmetricHelper2(TreeNode1* leftNode, TreeNode1* rightNode) {
    // 左子树和右子树都为空，对称
    if (leftNode == nullptr && rightNode == nullptr) {
        return true;
    }
    // 左子树或右子树有一个为空，不对称
    if (leftNode == nullptr || rightNode == nullptr) {
        return false;
    }
    // 判断左子树的左子树和右子树的右子树是否对称，以及左子树的右子树和右子树的左子树是否对称
    return (leftNode->val == rightNode->val) &&
        isSymmetricHelper2(leftNode->left, rightNode->right) &&
        isSymmetricHelper2(leftNode->right, rightNode->left);
}

// 判断二叉树是否对称
bool isSymmetric2(TreeNode1* root) {
    if (root == nullptr) {
        return true;
    }
    return isSymmetricHelper2(root->left, root->right);
}

int main_2() {
    string arrayString1;
    getline(cin, arrayString1);//getline可以读入空格，以换行结束


    // 解析输入字符串为字符串数组1
    vector<string> arr1;
    stringstream ss1(arrayString1);
    string token1;

    while (getline(ss1, token1, ',')) {
        arr1.push_back(token1);
    }
    //构建树
    TreeNode1* p = arrayToTree1(arr1);
    if (isSymmetric2(p)) {
        cout << "true" << endl;
    }
    else cout << "false" << endl;

    return 0;
}

/******************************************************************************
3: 翻转二叉树
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
*/
// 交换二叉树的左右子树

void swapLeftAndRight3(TreeNode1* root) {
    if (root == nullptr) {
        return;
    }
    // 交换左右子树
    TreeNode1* temp = root->left;
    root->left = root->right;
    root->right = temp;

    // 递归交换左右子树
    swapLeftAndRight3(root->left);
    swapLeftAndRight3(root->right);
}
//现在已经知道num
//算当前层数
int calculateHeight3(int num) {
    int height = 0;
    while (pow(2, height) - 1 < num) {
        height++;
    }
    return height;
}
//满二叉树最多有几个节点
int calculateNodeCount3(int height) {
    return pow(2, height) - 1;
}

// 层序遍历二叉树
void levelOrderTraversal3(TreeNode1* root,int num) {
    if (root == nullptr) {
        return;
    }
    queue<TreeNode1*> q;
    q.push(root);
    int i = 0,null=0;
    while (!q.empty()) {
        i++;
        TreeNode1* current = q.front();
        q.pop();
        if (current) {
            cout << current->val;
            if (current->left || current->right) {
                if (current->left) {
                    q.push(current->left);
                }
                else { 
                    q.push(nullptr); 
                    null++;
                }
                if (current->right) {
                    q.push(current->right);
                }
                else {
                    q.push(nullptr);
                    null++;
                }
            }
            else if (i < num) {
                q.push(nullptr);
                q.push(nullptr);
                null += 2;
            }
        }
        else {
            null--;
            cout << "null";
        }
        if (null == q.size()) break;
        if (!q.empty()) {
            cout << ",";
        }
    }
}

int main_3() {
    string arrayString1;
    getline(cin, arrayString1);//getline可以读入空格，以换行结束

    int num = 0;
    // 解析输入字符串为字符串数组1
    vector<string> arr1;
    stringstream ss1(arrayString1);
    string token1;

    while (getline(ss1, token1, ',')) {
        arr1.push_back(token1);
        num++;
    }
    int height = calculateHeight3(num);
    int num1 = calculateNodeCount3(height-1);

    //构建树
    TreeNode1* p = arrayToTree1(arr1);
    swapLeftAndRight3(p);
    levelOrderTraversal3(p,num1);
    return 0;
}//1,2,2,3,4,4,5,5,null,5,5,4,4,3,4,null,5,4

/*
4: 左叶子之和
题目描述
给定二叉树的根节点 root ，返回所有左叶子之和。

输入描述
一个节点序列
输出描述
返回其左叶子之和
*/

// 加二叉树左树叶子
void Addleft4(TreeNode1* root) {
    if (root == nullptr) {
        cout << "0" << endl;
        return;
    }
    if (!(root->left || root->right)) {
        cout << "0" << endl;
        return;
    }
    int num = 0;
    int flag = 0;
    queue<TreeNode1*> q;
    TreeNode1* a = new TreeNode1(-1);
    q.push(root);
    while (!q.empty()) {
        TreeNode1* current = q.front();
        q.pop();
        if (current-> val==- 1) {
            flag = 1;
            //cout << flag<<" "<<q.front()->val << endl;
            continue;
        }
        else if (current) {
            if (current->left || current->right) {
                if (current->left) {
                    q.push(a);//左子树前先加个-1进去
                    q.push(current->left);

                }
                if (current->right) {
                    q.push(current->right);
                }
                flag = 0;
            }
            else if (flag == 1 && current && !(current->left || current->right)) {
                // cout << current->val << endl;
                num += current->val;
                //cout << num << endl;
                flag = 0;
            }
            else;
        }
    }
    cout << num << endl;
}

int main_4() {
    string arrayString1;
    getline(cin, arrayString1);//getline可以读入空格，以换行结束

    // 解析输入字符串为字符串数组1
    vector<string> arr1;
    stringstream ss1(arrayString1);
    string token1;

    while (getline(ss1, token1, ',')) {
        arr1.push_back(token1);
    }

    //构建树
    TreeNode1* p = arrayToTree1(arr1);
    
    Addleft4(p);



    return 0;
}
/******************************************************************
5.*构建最小二叉搜索树
*/
// 递归构建二叉搜索树
//分治思想
int BSTnum = 0;
TreeNode1* buildBST5(vector<string> nums, int start, int end) {
    if (start > end) {
        return NULL;
    }
    else BSTnum++;
    int mid = 0;
    if (end - start % 2 == 0) {
         mid = start + (end - start) / 2;
    }
    else {
        mid = start + (end - start+1)/ 2;
    }
     
    //cout << mid << endl;
    TreeNode1* root = new TreeNode1(stoi(nums[mid]));

    root->left = buildBST5(nums, start, mid - 1);
    root->right = buildBST5(nums, mid + 1, end);

    return root;
}

// 创建高度最小的二叉搜索树
TreeNode1* createMinimalBST(vector<string> nums) {
   // cout << nums.size() - 1 << endl;
    return buildBST5(nums, 0, nums.size()-1);
}

int main_5() {
    string arrayString1;
    getline(cin, arrayString1);//getline可以读入空格，以换行结束

    // 解析输入字符串为字符串数组1
    vector<string> arr1;
    stringstream ss1(arrayString1);
    string token1;
    int num = 0;
    while (getline(ss1, token1, ',')) {
        arr1.push_back(token1);
        num++;
    }

    //构建树
    TreeNode1* p = createMinimalBST(arr1);
    int height = calculateHeight3(BSTnum);
    int num1 = calculateNodeCount3(height - 1);
    levelOrderTraversal3(p,num1);

    return 0;
}

/*
第6题 给定完美二叉树，填充每个右指针
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。

输入描述
给一个完美二叉树

输出描述
输出填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

输入输出样例
输入
root = [1,2,3,4,5,6,7]
输出
[1,#,2,3,#,4,5,6,7,#]
                                                      
输入
root = []
输出
[]
*/
//有next的树节点
struct TreeNextNode6 {
    int val;
    TreeNextNode6* left;
    TreeNextNode6* right;
    TreeNextNode6* next;
    TreeNextNode6(int x) : val(x), left(nullptr), right(nullptr), next(nullptr){}
};
int ErCiFang(int i) {
    int n = 2;
    int num = 0;
    while(1) {
        num += n;
        n *= 2;
        if (num == i) {
            return 1;
        }
        else if (num > i) {
            return 0;
        }
        else continue;
    }
}
//构造有next指针的树
//但给的数组里面没有null，因此不能直接给第9题用
TreeNextNode6* PerfectTree6(vector<string>& Tree) {
    if (Tree.empty()) {
        return nullptr;
    }
    TreeNextNode6 *root = new TreeNextNode6(stoi(Tree[0]));
    root->next = nullptr;
    queue<TreeNextNode6*> q;
    q.push(root);
    int i = 1;
    int ans = 0;
    while (1) {
        TreeNextNode6* current = q.front();
       // cout  << "存入:" << current->val<<endl;
        q.pop();
        ans++;
        //构建next指针
        if (!q.empty()) {
            TreeNextNode6* next = q.front();
            if (ErCiFang(ans-1)) {
                current->next = nullptr;
             //   cout << "产生一个#" << endl;
            }
            else { 
              //  cout<<current->val << "产生一个next是";
                current->next = next; 
           //     cout << next->val << endl;
            }
        }
       // 构建左子树节点
        if (i < Tree.size()) {
            current->left = new TreeNextNode6(stoi(Tree[i]));
            q.push(current->left);
            //cout << " mama" << current->val << "mama ";
        }
        i++;

        // 构建右子树节点
        if (i < Tree.size()){
            current->right = new TreeNextNode6(stoi(Tree[i]));
            q.push(current->right);   
        }
        i++;
        if (q.empty()) {
            break;
        }
       
    }
    return root;
}
// next层序遍历二叉树
void LevelTraversalPerfectTree6(TreeNextNode6* root) {//完美树不存在空树
    if (root == nullptr) {
        cout << ' ' << endl;
        return;
    }
    queue<TreeNextNode6*> q;
    q.push(root);
    while (root->left) {//先存入全部最左元素
        q.push(root->left);
        root = root->left;
    }
    while (!q.empty()) {
        TreeNextNode6* current = q.front();
        q.pop();
        while (current) {
            cout << current->val << ",";
            current = current->next;
        }
        if (!q.empty()) {
            cout << "#,";
        }
        else cout << "#" << endl;
    }
}
int main_6() {
    string arrayString1;
    getline(cin, arrayString1);//getline可以读入空格，以换行结束
    // 解析输入字符串为字符串数组1
    vector<string> arr1;
    stringstream ss1(arrayString1);
    string token1;

    while (getline(ss1, token1, ',')) {
        arr1.push_back(token1);
    }
    //构建完美树
    TreeNextNode6* p = PerfectTree6(arr1);
 //   cout << "构建成功" << endl;
    LevelTraversalPerfectTree6(p);
    return 0;
}
/*
7: 二叉树的最近公共祖先
题目描述
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
（一个节点也可以是它自己的祖先）。

输入描述
给一个二叉树
输出描述
输出它的最近公共近邻

输入输出样例
输入
root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出
3

输入
root = [1,2], p = 1, q = 2
输出
1
*/
struct ParentTreeNode7 {
    int val;
    int ans;
    ParentTreeNode7* left;
    ParentTreeNode7* right;
    ParentTreeNode7* parent;
    ParentTreeNode7(int x, int y) : val(x), ans(y),left(nullptr), right(nullptr), parent(nullptr) {}
};

// 将数组转换为有父母的层序二叉树的函数
ParentTreeNode7* ParentTree7(const vector<string>& arr) {
    if (arr.empty()) {  
        return nullptr;
    }
    int ans = 1;
    // 构建根节点
    ParentTreeNode7* root = new ParentTreeNode7(stoi(arr[0]),ans);
    root->parent = root;
    queue<ParentTreeNode7*> q;
    q.push(root);
    ans++;
    int i = 1;
    while (!q.empty() && i < arr.size()) {
        ParentTreeNode7* current = q.front();
        q.pop();
        //stoi是C++中的一个函数，用于将字符串转换为整数。它的完整名称是std::stoi，属于<string>头文件中的函数。
                // 构建左子树节点
        if (arr[i] != "null") {
            current->left = new ParentTreeNode7(stoi(arr[i]), ans);
            current->left->parent = current;
            q.push(current->left);
            ans++;
        }
        //else ans++;
        i++;

        // 构建右子树节点
        if (i < arr.size() && arr[i] != "null") {
            current->right = new ParentTreeNode7(stoi(arr[i]), ans);
            current->right->parent = current;
            q.push(current->right);
            ans++;
        }
        //else ans++;
        i++;
    }
    return root;
}
//层序遍历到p然后指针停在那里
ParentTreeNode7* Findpq7(ParentTreeNode7* root, int p) {
    if (root == nullptr) {
        return root;
    }
    queue<ParentTreeNode7*> q;
    q.push(root);
    ParentTreeNode7* current = q.front();
    while (!q.empty()) {
        ParentTreeNode7* current = q.front();
        q.pop();
        if (current->ans == p) return current;
        if (current->left) {
            q.push(current->left);
        }
        if (current->right) {
            q.push(current->right);
        }
    }
    return current;
}
void FindSameParent7(ParentTreeNode7* root,int p,int q){
    //层序遍历到p然后指针停在那里
    ParentTreeNode7* a = Findpq7(root, p);
   // cout << "a查找成功:ans为" <<a->ans<< "val为" << a->val<< endl;
    ParentTreeNode7* b = Findpq7(root, q);
   // cout << "b查找成功:ans为" << b->ans<< "val为" << b->val<<endl;
    while (1) {
       // cout << "********遍历查找*********"<< endl;
        if (a->parent == b->parent) {//当前就已经相同
            cout << a->parent->val << endl;
            break;
        }
        else if (a == b->parent) {
            cout << a->val << endl;
            break;
        }
        else if (a->parent == b) {
            cout << b->val << endl;
            break;
        }
        //else if (a->parent == root || b->parent == root) {//遍历到底
          //  cout << "输出了root值" << endl;
          //  cout << root->val << endl;
           // break;
      //  }
        else if (a->parent->ans < b->parent->ans) {
          // cout << "b+1此时a的ans比b小,a为" << a->parent->ans << ",b为" << b->parent->ans << endl;
            b = b->parent;
        }
        else if (a->parent->ans > b->parent->ans) {
           // cout << "a+1此时b的ans比a小,a为" << a->parent->ans << ",b为" << b->parent->ans << endl;
            a = a->parent;
        }
        else continue;
    }
}

int main_7() {
    string arrayString1;
    getline(cin, arrayString1);//getline可以读入空格，以换行结束
    // 解析输入字符串为字符串数组1
    vector<string> arr1;
    stringstream ss1(arrayString1);
    string token1;

    while (getline(ss1, token1, ',')) {
        arr1.push_back(token1);
    }

    int p = 0, q = 0;
    cin >> p >> q;
    //构建父母树
    ParentTreeNode7* root = ParentTree7(arr1);
   // cout << "构建成功" << endl;
    FindSameParent7(root, p, q);


    return 0;
}

/*第八题，给了二叉搜索树
* 8: 恢复二叉搜索树
题目描述
给你二叉搜索树的根节点 root ，该树中的 恰好 两个节点的值被错误地交换。请在不改变其结构的情况下，恢复这棵树 。

输入描述
给一个二叉树
输出描述
恢复这棵树

输入输出样例
输入
root = [1,3,null,null,2]
输出
[3,1,null,null,2]

输入
Root = [3,1,4,null,null,2]
输出
[2,1,4,null,null,3]
**********提醒：
* 二叉搜索树满足任意节点的左子树们恒定小于它，右边大于它
* 此处只有两个节点值，因此我们最笨的想法就是固定一个节点往下遍历它的有没有不符合的，直到结束
* 优化算法，，，，，待会看题解

*/

//可考虑输出中序遍历，然后存成数组，数组里面的只有两个数字有问题，交换即可

//构造已知二叉搜索树，可以调用树生成那个函数，他给的就是层序遍历
TreeNode1 *FindWrongNode8(TreeNode1* root) {//返回那个跟它错误的节点
    queue<TreeNode1*> left;//左边
    if (root->left) {
        if (root->left->val > root->val) {
            return root->left;
        }
        left.push(root->left);
        while (!left.empty()) {
            TreeNode1* current = left.front();
            left.pop();
            //保证每个存进队列
            if (current->left) {
                left.push(current->left);
            }
            if (current->right) {
                left.push(current->right);
            }
            if (current->val > root->val) {
                return current;
            }
        }
    }

    queue<TreeNode1*> right;
    if (root->right ) {
        if (root->right->val < root->val) {
            return root->right;
        }
        right.push(root->right);
        while (!right.empty()) {
            TreeNode1* current = right.front();
            right.pop();
            //保证每个存进队列
            if (current->left) {
                right.push(current->left);
            }
            if (current->right) {
                right.push(current->right);
            }
            if (current->val < root->val) {
                return current;
            }
        }
    }  
}
TreeNode1* RepirWrongTree8(TreeNode1* root) {
    //1.固定一个，看左右子树有无问题
    //2.可以爆破，层序遍历每一个，
    //因为只有两个不同，将每个节点看成root找子树，找到就交换val，break
    //3.返回root根节点
    queue<TreeNode1*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode1* current = q.front();
        q.pop();
        //保证每个存进队列
        if (current->left) {
            q.push(current->left);
        }
        if (current->right) {
            q.push(current->right);
        }
        //查找当前的Node下是否有错误
        //有则交换val并退出
        //无则继续往下检索
        TreeNode1* Wrong = FindWrongNode8(current);
        if (Wrong != current) {//如果不等交换退出循环
            int temp = Wrong->val;
            Wrong->val = current->val;
            current->val = temp;
            break;
        } 
    }
    return root;
}


int main_8() {
    string arrayString1;
    int num = 0;

    getline(cin, arrayString1);//getline可以读入空格，以换行结束
    // 解析输入字符串为字符串数组1
    vector<string> arr1;
    stringstream ss1(arrayString1);
    string token1;

    while (getline(ss1, token1, ',')) {
        arr1.push_back(token1);
        num++;
    }
    //num辅助待会输出
    int height = calculateHeight3(num);
    int num1 = calculateNodeCount3(height - 1);

    TreeNode1* root = arrayToTree1(arr1);//构建树
    root = RepirWrongTree8(root);//修复树
    
    levelOrderTraversal3(root,num1);//输出现在的树
    return 0;
}

/************************第9题*************************
* 
* 9: 奇偶数
题目描述
如果一棵二叉树满足下述几个条件，则可以称为 奇偶树 ：
二叉树根节点所在层下标为 0 ，根的子节点所在层下标为 1 ，根的孙节点所在层下标为 2 ，依此类推。
偶数下标 层上的所有节点的值都是 奇 整数，从左到右按顺序 严格递增
奇数下标 层上的所有节点的值都是 偶 整数，从左到右按顺序 严格递减
给你二叉树的根节点，如果二叉树为 奇偶树 ，则返回 true ，否则返回 false 。

输入描述
给一个二叉树
输出描述
判断是否是奇偶树

输入输出样例
输入
root = [1,10,4,3,null,7,9,12,8,6,null,null,2]
输出
true
输入

root = [2,1,3]
输出
false


*/

//题目要求
//1.偶数层为奇整数、递增
//2.奇数层为偶整数、递减

//考虑，，设置计层器，利用队列，对每层单独判断
bool isEvenOddTree9(TreeNode1* root) {
    queue<TreeNode1*> queue;
    int level = 0;
    queue.push(root);
    while (!queue.empty()) {
        int size = queue.size();
        int preVal = level % 2 == 0 ? 0 : 1000001;
        for (int i = 0; i < size; i++) {//每一次处理一层，把一层的全部pop出去后开始下一层
            TreeNode1* node = queue.front();
            queue.pop();
            int val = node->val;
            if (level % 2 == val % 2) {
                return false;
            }
            if ((level % 2 == 0 && val <= preVal) || (level % 2 == 1 && val >= preVal)) {
                return false;
            }
            if (node->left != nullptr) {
                queue.push(node->left);
            }
            if (node->right != nullptr) {
                queue.push(node->right);
            }
            preVal = val;
        }
        level++;
    }
    return true;
}

int main_9() {
    string arrayString1;
    getline(cin, arrayString1);//getline可以读入空格，以换行结束
    // 解析输入字符串为字符串数组1
    vector<string> arr1;
    stringstream ss1(arrayString1);
    string token1;

    while (getline(ss1, token1, ',')) {
        arr1.push_back(token1);
    }
    //构建奇偶树
    TreeNode1* root = arrayToTree1(arr1);
    
    //判断是否为奇偶树
    if (isEvenOddTree9(root)) {
        cout << "true" << endl;
    }
    else cout << "false" << endl;
  
    return 0;
}


/*10
 10.二叉树的子树大小
描述
现在给出一棵二叉树，希望你输出它的每一个结点为根的子树大小

输入
第一行一个正整数 n，表示给定的树的节点的数目，规定节点编号 1∼n，其中节点 1是树根。
接下来 n 行，每行两个正整数 li, ri  ，分别表示节点 i 的左右孩子的编号。
如果不存在左 / 右孩子，则以 −1 表示。两个数之间用一个空格隔开。

输出
一行，n个数，分别表示i号结点为根的子树的子树大小

样例
输入

3
2 3
-1 -1
-1 -1
输出

3 1 1

*/
//思考了一下之后可以直接用顺序存储
//不用链表，定义数据结构，然后用数组
struct TreeNode10{
    int left;
    int right;
};

vector<int> subtreeSizes;

int getSubtreeSize10(int root, const vector<TreeNode10>& tree) {
    if (root == -1) {
        return 0;
    }

    int leftSize = getSubtreeSize10(tree[root].left, tree);
    int rightSize = getSubtreeSize10(tree[root].right, tree);

    int currentSize = leftSize + rightSize + 1;
    subtreeSizes[root] = currentSize;

    return currentSize;
}

int main_10() {
    int n;
    cin >> n;

    vector<TreeNode10> tree(n + 1);  // 为了与题目中的节点编号从1开始保持一致，使用大小为n+1的vector

    // 读取树的信息
    for (int i = 1; i <= n; i++) {
        cin >> tree[i].left >> tree[i].right;
    }

    subtreeSizes.resize(n + 1);  // 初始化存储子树大小的数组

    // 计算每个结点为根的子树大小
    getSubtreeSize10(1, tree);

    // 输出结果
    for (int i = 1; i <= n; i++) {
        cout << subtreeSizes[i] << " ";
    }

    return 0;
}

/*
11题，11题很好，和10题很像，相当于多了一个节点自身代值
11: 二叉树的子树和
描述
现在给出一棵二叉树，每个结点有一个权值，希望你依次输出每一个节点为根的子树的子树权值和

输入
第一行一个正整数 n，表示给定的树的节点的数目，规定节点编号 1∼n，其中节点 1是树根。
第二行 n 个正整数，用一个空格分隔，第 i 个正整数vi，代表节点 i 的权值。
接下来 n 行，每行两个正整数 li, ri  ，分别表示节点 i 的左右孩子的编号。
如果不存在左 / 右孩子，则以 −1 表示。两个数之间用一个空格隔开。

输出
一行，n个数，分别表示i号结点为根的子树的子树权值和

样例
输入

3
1 1000 1000
2 3
-1 -1
-1 -1
输出

2001 1000 1000
*/
//加了power的长数组
struct TreeNode11 {
    int left;
    int right;
    int power;
};

vector<int> subtreePowers;

int getSubtreePower11(int root, const vector<TreeNode11>& tree) {
    if (root == -1) {
        return 0;
    }

    int leftPower = getSubtreePower11(tree[root].left,tree);
    int rightPower = getSubtreePower11(tree[root].right, tree);

    int currentPower = leftPower + rightPower + tree[root].power;
    subtreePowers[root] = currentPower;

    return currentPower;
}

int main_11() {
    int n;
    cin >> n;

    vector<TreeNode11> tree(n + 1);  // 为了与题目中的节点编号从1开始保持一致，使用大小为n+1的vector
    for (int i = 1; i <= n; i++) {
        cin >> tree[i].power;
    }
    // 读取树的信息
    for (int i = 1; i <= n; i++) {
        cin >> tree[i].left >> tree[i].right;
    }

    subtreePowers.resize(n + 1);  // 初始化存储子树大小的数组

    // 计算每个结点为根的子树大小
    getSubtreePower11(1, tree);

    // 输出结果
    for (int i = 1; i <= n; i++) {
        cout << subtreePowers[i] << " ";
    }

    return 0;
}

/*
12: 确定树的形态
描述
现在给出一棵二叉树的前序遍历和后序遍历，输出树的后序遍历

输入
第一行一个正整数 n，表示给定的树的节点的数目，规定节点编号 1∼n，其中节点 1是树根。
第二行 n 个正整数，用一个空格分隔，代表二叉树的前序遍历
第三行 n 个正整数，用一个空格分隔，代表二叉树的中序遍历

输出
一行，n个数，用一个空格分隔，表示二叉树的后序遍历

样例
输入

3
1 2 3
2 1 3
输出

2 3 1
*/

//没想到，后面几个考遍历方法
/*
已知该二叉树的先序遍历序列为：A-B-D-E-G-C-F，中序遍历序列为：D-B-G-E-A-C-F。

第一步：找根 先序遍历先遍历根结点 那么它的序列第一个肯定是根节点也就是上面的A

第二步：找根结点的左右子数 中序遍历先左后根后右 
在中序序列中找到根结点的位置那么它的左边就是它的左子树序列 右边就是它的右子数序列
即上面的 D-B-G-E 和 C-F

第三步：拆分转化为子问题 去掉A结点 将树分为两个二叉树 B-D-E-G 和C-F
然后按照第一步分别找两颗树的根 B C 然后根据第二部找根的左右子数
B(左边D 右边 G-E) C (左边NULL 右边 F) 一次类推 直到还原出二叉树的模型

*/
struct Node
{
    int data;
    Node* left;
    Node* right;
};

Node* getBinaryTree(int* preOrder, int* inOrder, int len)
{
    if (preOrder == nullptr || len <= 0)
        return nullptr;

    Node* root = new Node;
    root->data = *preOrder; // 前序遍历的第一个节点就是根节点

    // 找到根节点在中序遍历中的位置，其值也代表了左子树的节点数目
    int pos = 0;
    while (inOrder[pos] != root->data)
    {
        pos++;
    }

    // 递归找到左子树和右子树
    if (0 == pos)
    {
        root->left = nullptr;
    }
    else
    {
        root->left = getBinaryTree(preOrder + 1, inOrder, pos);
    }

    if (0 == len - pos - 1)
    {
        root->right = nullptr;
    }
    else
    {
        root->right = getBinaryTree(preOrder + pos + 1, inOrder + pos + 1, len - pos - 1);
    }

    return root;
}

void postOrder(Node* root)
{
    if (root == nullptr)
        return;

    postOrder(root->left);
    postOrder(root->right);
    cout << root->data<<" ";
}

int main_12()
{
    int len;
    cin >> len;

    int* preOrder = new int[len];//preOder指向数组起始0处
    int* inOrder = new int[len];

    for (int i = 0; i < len; ++i)
    {
        cin >> preOrder[i];
    }

    for (int i = 0; i < len; ++i)
    {
        cin >> inOrder[i];
    }

    Node* root = getBinaryTree(preOrder, inOrder, len);
    postOrder(root);

    delete[] preOrder;
    delete[] inOrder;

    return 0;
}

/*
13.构建哈夫曼树
哈夫曼叔的带权路径长
描述
现在给出一棵二叉树，每个结点有一个权值，希望你构造赫夫曼树，并输出其对应的带权路径长度

输入
第一行一个正整数 n，表示给定的树的节点的数目，规定节点编号 1∼n。
第二行 n 个正整数，用一个空格分隔，第 i 个正整数vi，代表节点 i 的权值。

输出
一个数，表示对应赫夫曼树的带权路径长度

样例
输入

3
1 1000 1000
输出

3002
*/
//构建哈夫曼树的基本思想
/*
1.权值最小的在越后端        基本要求
2.每次找到最小的两个权值，合成左右子树      函数1，Select两个最小节点不断合并
3.root的权值=左加右，然后更新节点即可              函数2，构建哈夫曼树，不断调用函数1，最后只剩根节点
4.计算带权路径长度总和       函数3：计算全部
*/

//哈夫曼树的标准定义
typedef struct
{
    int weight;   // 结点的权值，为了方便直接用int
    int parent, lchild, rchild;  // 左右孩子和双亲
} HTNode, * HuffmanTree;

// 选择权值最小的两个结点
void Select(HuffmanTree HT, int n, int& index1, int& index2) {
    if (n <= 1)
        return;

    index1 = index2 = 0;

    for (int k = 1; k <= n; k++) {   //给index1赋初值
        if (HT[k].parent == 0) {
            index1 = k;
            break;
        }
    }

    for (int k = 1; k <= n; k++) {   //给index2赋初值
        if (HT[k].parent == 0 && k != index1) {
            index2 = k;
            break;
        }
    }

    for (int k = 1; k <= n; k++) {   //找到最小的权值,赋给index1
        if (HT[k].parent == 0 && k != index2) {
            if (HT[index1].weight > HT[k].weight) {
                index1 = k;
            }
        }
    }

    HT[index1].parent = -1;  //将最小的权值结点双亲改为-1，防止被index2选取

    for (int i = 1; i <= n; i++) {   //找到第二小的权值,赋给index2
        if (HT[i].parent == 0 && i != index1) {
            if (HT[index2].weight > HT[i].weight) {
                index2 = i;
            }
        }
    }
}

// 构建哈夫曼树
// HT为树,n为叶子结点数,w[]叶子的权值
void CreateHuffmanTree(HuffmanTree& HT, int n, int w[]) {
    if (n <= 1) // 如果结点小于等于1,直接退出
        return;

    int m = 2 * n - 1;  //总共有2*n-1个结点
    HT = new HTNode[m + 1]; //为了方便,不用0号单元，HT[m]表示根结点,下表从1开始

    /*给所有结点的左,右孩子以及双亲初始化为0;*/
    for (int i = 1; i <= m; ++i)
    {
        HT[i].lchild = 0;
        HT[i].rchild = 0;
        HT[i].parent = 0;
    }

    /*给前 n 个结点设置权重*/
    for (int i = 1; i <= n; i++)
    {
        HT[i].weight = w[i];
    }

    /*给第 n 个结点之后的结点赋值,以及设置左右孩子和双亲*/
    for (int i = n + 1; i <= m; ++i) {
        int s1 = -1, s2 = -1; // s1 和 s2 分别为权值最小和次小的结点下标

        /*
            调用Select函数
            在前 i-1 个没有双亲的结点中返回权重最小的结点序号s1,s2
        */
        Select(HT, i - 1, s1, s2);

        /*
            将第 s1,s2 号结点的双亲设置为第 i 个结点
            同时意味着下次调用Select函数将忽略s1,s2
        */
        HT[s1].parent = i;
        HT[s2].parent = i;

        /*s1,s2分别作为i的左右孩子*/
        HT[i].lchild = s1;
        HT[i].rchild = s2;

        /*i 的权值为左右孩子权值之和*/
        HT[i].weight = HT[s1].weight + HT[s2].weight;
    }
}

// 计算哈夫曼树的带权路径长度
int CalculateWPL(const HuffmanTree& HT, int n) {
    int wpl = 0;
    for (int i = 1; i <= n; ++i) {
        int depth = 0;
        int j = i;
        while (HT[j].parent != 0) {
            j = HT[j].parent;
            depth++;
        }
        wpl += HT[i].weight * depth;
    }
    return wpl;
}

int main() {
    int n;
    cin >> n;

    int* weights = new int[n + 1];  // 为了方便，不使用0号单元
    for (int i = 1; i <= n; ++i) {
        cin >> weights[i];
    }

    HuffmanTree ht;
    CreateHuffmanTree(ht, n, weights);

    int wpl = CalculateWPL(ht, n);
    cout  << wpl << endl;

    delete[] ht;  // 释放动态分配的内存
    delete[] weights;  // 释放动态分配的内存

    return 0;
}
数据结构与算法
# 二叉树部分题解

Pwn复习-初级ROP

2023大创介绍
