博客详情 - XJYOJ

juxq's blog
二叉树经典例题
指导教师 (juxq) LV 2 SU @ 2023-6-28 1:53:06

LCT0226 翻转二叉树

// 二叉树结构体指针解法

#include <bits/stdc++.h>
using namespace std;

struct TreeNode { // 定义二叉树的结点结构体
    int val; // 结点的值
    TreeNode *left; // 左子结点
    TreeNode *right; // 右子结点
    TreeNode() : val(INT_MIN), 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) {} // 构造函数
};

TreeNode* invertTree(TreeNode* root) {
    if (root == nullptr) { // 如果二叉树为空
        return nullptr; // 返回空指针
    }
    TreeNode* left = invertTree(root->left); // 将左子树的根结点赋值给指针变量left
    TreeNode* right = invertTree(root->right); // 将右子树的根结点赋值给指针变量right
    root->left = right; // 将指针变量right赋值给结点root的左子结点
    root->right = left; // 将指针变量left赋值给结点root的右子结点
    return root; // 返回结点root
}

TreeNode *buildTree(vector<int> &nums, int index) { // 建立二叉树
    if (index >= int(nums.size())) { // 如果index大于等于数组nums的长度
        return nullptr; // 返回空指针
    }
    TreeNode *root = new TreeNode(nums[index]); // 创建二叉树的根结点
    root->left = buildTree(nums, 2 * index + 1); // 创建二叉树的左子树
    root->right = buildTree(nums, 2 * index + 2); // 创建二叉树的右子树
    return root; // 返回结点root
}

void printLevelOrder(TreeNode *root) { // 层序遍历输出
    if (!root) return;
    queue<TreeNode *> que;
    que.push(root);
    while (!que.empty()) {
        TreeNode *p = que.front();
        que.pop();
        cout << p->val << " ";
        if (p->left) que.push(p->left);
        if (p->right) que.push(p->right);
    }
}

void printPreOrder(TreeNode *root) { // 先序遍历输出
    if (!root) return;
    cout << root->val << " ";
    printPreOrder(root->left);
    printPreOrder(root->right);
}

void printInOrder(TreeNode *root) { // 中序遍历输出
    if (!root) return;
    printInOrder(root->left);
    cout << root->val << " ";
    printInOrder(root->right);
}

void printPostOrder(TreeNode *root) { // 后序遍历输出
    if (!root) return;
    printPostOrder(root->left);
    printPostOrder(root->right);
    cout << root->val << " ";
}

int main() {
    int num;
    vector<int> nums; // 定义vector容器nums
    while(cin >> num) nums.push_back(num); // 输入二叉树的结点值
    TreeNode *root = buildTree(nums, 0); // 建立二叉树
    TreeNode *ans = invertTree(root); // 将函数invertTree的返回值赋值给指针变量ans
    printLevelOrder(ans); // 层序遍历输出
    return 0;
}

LCT0102 二叉树的层序遍历

// 二叉树的层序遍历：队列，将根节点入队，当队列不为空时，将队列中的元素出队，将出队元素的左右子树入队，将出队元素的值加入到数组中

#include <bits/stdc++.h>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode() : val(INT_MIN), left(nullptr), right(nullptr) {}   // 构造函数
    TreeNode(int _val) : val(_val), left(nullptr), right(nullptr) {}   // 构造函数
    TreeNode(int _val, TreeNode *_left, TreeNode *_right) : val(_val), left(_left), right(_right) {}   // 构造函数
};

vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> res; // 定义二维数组
    if (!root) return res; // 如果根节点为空，返回空数组
    queue<TreeNode*> q; // 定义队列
    q.push(root); // 将根节点入队
    while (!q.empty()) { // 当队列不为空时
        int size = q.size(); // 定义size等于队列的大小
        vector<int> tmp; // 定义一维数组
        for (int i = 0; i < size; i++) { // 遍历队列
            TreeNode *node = q.front(); // 定义node等于队首元素
            q.pop(); // 将队首元素出队
            tmp.push_back(node->val); // 将队首元素的值加入到一维数组中
            if (node->left) q.push(node->left); // 如果队首元素的左子树不为空，将左子树入队
            if (node->right) q.push(node->right); // 如果队首元素的右子树不为空，将右子树入队
        }
        res.push_back(tmp); // 将一维数组加入到二维数组中
    }
    return res; // 返回二维数组
}

TreeNode *buildTree(vector<int> &nums, int index) { // 建立二叉树
    if (index >= int(nums.size()) || nums[index] == INT_MIN) return nullptr; // 如果index大于等于数组长度或者数组元素为-1，返回空指针
    TreeNode *root = new TreeNode(nums[index]); // 建立根节点
    root->left = buildTree(nums, 2 * index + 1); // 建立左子树
    root->right = buildTree(nums, 2 * index + 2); // 建立右子树
    return root; // 返回根节点
}

int main() {
    string s;
    int num;
    vector<int> nums;
    while (cin >> s) {
        if (s == "null") num = INT_MIN; // 如果s等于null，num等于 INT_MIN
        else num = stoi(s); // 否则num等于s
        nums.push_back(num);
        if (cin.get() == '\n') break;
    } 
    TreeNode *root = buildTree(nums, 0); // 建立二叉树
    vector<vector<int>> res = levelOrder(root); // 二叉树的层序遍历
    for (int i = 0; i < int(res.size()); i++) { // 遍历二维数组
        for (int j = 0; j < int(res[i].size()); j++) { // 遍历一维数组
            cout << res[i][j] << " "; // 输出数组元素
        }
        cout << endl;
    }
    return 0;
}

LCT0101 对称二叉树

// 对称二叉树：递归，如果左子树的左子树等于右子树的右子树，且左子树的右子树等于右子树的左子树，说明是对称二叉树

#include <bits/stdc++.h>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode() : val(INT_MIN), left(nullptr), right(nullptr) {}   // 构造函数
    TreeNode(int _val) : val(_val), left(nullptr), right(nullptr) {}   // 构造函数
    TreeNode(int _val, TreeNode *_left, TreeNode *_right) : val(_val), left(_left), right(_right) {}   // 构造函数
};

bool isSymmetric(TreeNode* left, TreeNode* right) {
    if (!left && !right) return true; // 如果左子树和右子树都为空，返回true
    if (!left || !right) return false; // 如果左子树和右子树有一个为空，返回false
    return left->val == right->val && isSymmetric(left->left, right->right) && isSymmetric(left->right, right->left); // 返回左子树的左子树等于右子树的右子树，且左子树的右子树等于右子树的左子树
}

bool isSymmetric(TreeNode* root) {
    if (!root) return true; // 如果根节点为空，返回true
    return isSymmetric(root->left, root->right); // 返回左子树和右子树是否对称
}

TreeNode *buildTree(vector<int> &nums, int index) { // 建立二叉树
    if (index >= int(nums.size()) || nums[index] == INT_MIN) return nullptr; // 如果index大于等于数组长度或者数组元素为-1，返回空指针
    TreeNode *root = new TreeNode(nums[index]); // 建立根节点
    root->left = buildTree(nums, 2 * index + 1); // 建立左子树
    root->right = buildTree(nums, 2 * index + 2); // 建立右子树
    return root; // 返回根节点
}

int main() {
    string s;
    int num;
    vector<int> nums;
    while (cin >> s) {
        if (s == "null") num = INT_MIN; // 如果s等于null，num等于 INT_MIN
        else num = stoi(s); // 否则num等于s
        nums.push_back(num);
        if (cin.get() == '\n') break;
    } 
    TreeNode *root = buildTree(nums, 0); // 建立二叉树
    bool res = isSymmetric(root); // 判断是否是对称二叉树
    cout << (res ? "true" : "false") << endl;
    return 0;
}

LCT0104 二叉树的最大深度

#include <bits/stdc++.h>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode() : val(INT_MIN), left(nullptr), right(nullptr) {}   // 构造函数
    TreeNode(int _val) : val(_val), left(nullptr), right(nullptr) {}   // 构造函数
    TreeNode(int _val, TreeNode *_left, TreeNode *_right) : val(_val), left(_left), right(_right) {}   // 构造函数
};

int maxDepth(TreeNode* root) {
    if (!root) return 0; // 如果根节点为空，返回0
    return max(maxDepth(root->left), maxDepth(root->right)) + 1; // 返回左子树的最大深度和右子树的最大深度的最大值加1
}

TreeNode *buildTree(vector<int> &nums, int index) { // 建立二叉树
    if (index >= int(nums.size()) || nums[index] == INT_MIN) return nullptr; // 如果index大于等于数组长度或者数组元素为-1，返回空指针
    TreeNode *root = new TreeNode(nums[index]); // 建立根节点
    root->left = buildTree(nums, 2 * index + 1); // 建立左子树
    root->right = buildTree(nums, 2 * index + 2); // 建立右子树
    return root; // 返回根节点
}

int main() {
    string s;
    int num;
    vector<int> nums;
    while (cin >> s) {
        if (s == "null") num = INT_MIN; // 如果s等于null，num等于 INT_MIN
        else num = atoi(s.c_str()); // 否则num等于s
        nums.push_back(num);
        if (cin.get() == '\n') break;
    } 
    TreeNode *root = buildTree(nums, 0); // 建立二叉树
    int res = maxDepth(root);
    cout << res << endl;
    return 0;
}

LCT0124 二叉树的最大路径和

#include <bits/stdc++.h>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int _val) : val(_val), left(nullptr), right(nullptr) {}
    TreeNode(int _val, TreeNode *_left, TreeNode *_right) : val(_val), left(_left), right(_right) {}
};

int res = INT_MIN;

int dfs(TreeNode *root) {
    if (!root) return 0;
    int left = max(0, dfs(root->left));
    int right = max(0, dfs(root->right));
    res = max(res, left + right + root->val);
    return max(left, right) + root->val;
}

int maxPathSum(TreeNode *root) {
    dfs(root);
    return res;
}

int main() {
    int val;
    string s;
    cin >> val;
    TreeNode *root = new TreeNode(val);
    queue<TreeNode*> q;
    q.push(root);
    while (cin >> s) {
        if (s == "null") {
            q.front()->left = nullptr;
        } else {
            val = stoi(s);
            TreeNode *node = new TreeNode(val);
            q.front()->left = node;
            q.push(node);
        }
        cin >> s;
        if (s == "null") {
            q.front()->right = nullptr;
        } else {
            val = stoi(s);
            TreeNode *node = new TreeNode(val);
            q.front()->right = node;
            q.push(node);
        }
        q.pop();
        if (cin.get() == '\n') break;
    }
    cout << maxPathSum(root) << endl;
    return 0;
}

LCT0987 二叉树的垂直遍历

// 深搜

#include <bits/stdc++.h>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int _val) : val(_val), left(nullptr), right(nullptr) {}
    TreeNode(int _val, TreeNode *_left, TreeNode *_right) : val(_val), left(_left), right(_right) {}
};

void dfs(TreeNode *root, int x, int y, map<int, map<int, vector<int>>> &mp) {
    if (root == nullptr) return ;
    mp[x][y].push_back(root->val);   // 将节点的值加入到哈希表中
    dfs(root->left, x - 1, y + 1, mp);   // 递归遍历左子树
    dfs(root->right, x + 1, y + 1, mp);   // 递归遍历右子树
}

vector<vector<int>> verticalTraversal(TreeNode *root) {
    map<int, map<int, vector<int>>> mp;   // 定义哈希表
    dfs(root, 0, 0, mp);   // 递归遍历二叉树
    vector<vector<int>> res;
    for (auto it1 = mp.begin(); it1 != mp.end(); it1++) {   // 遍历哈希表
        vector<int> tmp;
        for (auto it2 = it1->second.begin(); it2 != it1->second.end(); it2++) {   // 遍历哈希表
            sort(it2->second.begin(), it2->second.end());   // 对哈希表中的值进行排序
            for (auto it3 = it2->second.begin(); it3 != it2->second.end(); it3++) {   // 遍历哈希表
                tmp.push_back(*it3);   // 将哈希表中的值加入到临时数组中
            }
        }
        res.push_back(tmp);   // 将临时数组加入到结果数组中
    }
    return res;
}

int main() {
 int val;
    string s;
    cin >> val;
    TreeNode *root = new TreeNode(val);
    queue<TreeNode*> q;
    q.push(root);
    while (cin >> s) {
        if (s == "null") {
            q.front()->left = nullptr;
        } else {
            val = stoi(s);
            TreeNode *node = new TreeNode(val);
            q.front()->left = node;
            q.push(node);
        }
        cin >> s;
        if (s == "null") {
            q.front()->right = nullptr;
        } else {
            val = stoi(s);
            TreeNode *node = new TreeNode(val);
            q.front()->right = node;
            q.push(node);
        }
        q.pop();
        if (cin.get() == '\n') break;
    }
    vector<vector<int>> res = verticalTraversal(root);
    for (int i = 0; i < int(res.size()); i++) {
        for (int j = 0; j < int(res[i].size()); j++) {
            cout << res[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

二叉树经典例题

LCT0226 翻转二叉树

LCT0102 二叉树的层序遍历

LCT0101 对称二叉树

LCT0104 二叉树的最大深度

LCT0124 二叉树的最大路径和

LCT0987 二叉树的垂直遍历

还没有账户？

登录