2024.06.21 刷题日记

本文主要是介绍2024.06.21 刷题日记，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

101. 对称二叉树

判断是否对称，检查 root->left->val == root->right->val，接着进行递归检查对称位置：

class Solution {
public:// 传入对称位置的两个对称位置bool isMirror(TreeNode* left, TreeNode* right) {if (!left && !right)return true;if (!left || !right)return false;if (left->val != right->val)return false;return isMirror(left->left, right->right) &&isMirror(left->right, right->left);}bool isSymmetric(TreeNode* root) {if (!root)return true;return isMirror(root->left, root->right);}
};

543. 二叉树的直径

求二叉树的直径，就是在求当前节点左子树的深度和右子树的深度，两者一加，然后求最大值就可以了：

class Solution {
private:int maxDiameter = 0;int maxDepth(TreeNode* node) {if (!node)return 0;int leftMax = maxDepth(node->left);int rightMax = maxDepth(node->right);maxDiameter = max(leftMax + rightMax, maxDiameter);return max(leftMax, rightMax) + 1;}public:int diameterOfBinaryTree(TreeNode* root) {maxDepth(root); // 开始递归计算深度，并更新直径return maxDiameter;}
};

102. 二叉树的层序遍历

这个就是 bfs，直接利用队列：

class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {deque<TreeNode*> que; // 性能好if (!root)return {};vector<vector<int>> ans;vector<int> ansi;que.push_back(root);while (!que.empty()) {// 一次处理一层int levelSize = que.size();for (int i = 0; i < levelSize; i++) {TreeNode* temp = que.front();que.pop_front();ansi.push_back(temp->val);if (temp->left)que.push_back(temp->left);if (temp->right)que.push_back(temp->right);}ans.push_back(std::move(ansi));}return ans;}
};

108. 将有序数组转换为二叉搜索树

这道题的思路是，直接找数组的中间节点为根节点，这把数组分为两部分，然后递归创建二叉树：

class Solution {
public:TreeNode* sortedArrayToBST(vector<int>& nums) {return createBST(nums, 0, nums.size() - 1);}TreeNode* createBST(const vector<int>& nums, int left, int right) {if (left > right) {return nullptr; }int mid = left + (right - left) / 2;TreeNode* node = new TreeNode(nums[mid]);node->left = createBST(nums, left, mid - 1);node->right = createBST(nums, mid + 1, right);return node;}
};

98. 验证二叉搜索树

依然是递归的思路：每次将当前节点的值作为验证左子树的最大值，作为验证右子树的最大值：

class Solution {
public:bool isValidBST(TreeNode* root) {return isValidBSTHelper(root, LONG_MIN, LONG_MAX);}private:bool isValidBSTHelper(TreeNode* node, long minVal, long maxVal) {if (!node)return true;if (node->val <= minVal || node->val >= maxVal)return false;return isValidBSTHelper(node->left, minVal, node->val) &&isValidBSTHelper(node->right, node->val, maxVal);}
};

230. 二叉搜索树中第K小的元素

这是搜索树，而搜索树的中序遍历顺序就是有序，因此可以中序遍历此树，然后将第 k 个值赋给变量 result ，然后返回：

class Solution {
public:int kthSmallest(TreeNode* root, int k) {int count = 0; int result = 0;inorder(root, k, count, result);return result;}private:void inorder(TreeNode* node, int k, int& count, int& result) {if (!node)return;// 遍历左子树inorder(node->left, k, count, result);// 访问当前节点++count;if (count == k) {result = node->val; return;  }// 遍历右子树inorder(node->right, k, count, result);}
};

总结

1. 对称二叉树 (LeetCode 101):

   • 通过递归检查树的左右子树是否是镜像对称的。这涉及到对树的每个节点进行比较。

2. 二叉树的直径 (LeetCode 543):

   • 计算每个节点的左右子树的最大深度，然后用它们的和更新最大直径。这也是通过递归实现的。

3. 二叉树的层序遍历 (LeetCode 102):

   • 使用队列进行广度优先搜索（BFS），一层层地处理树中的每个节点。

4. 将有序数组转换为二叉搜索树 (LeetCode 108):

   • 通过递归选择数组的中间元素作为树的节点，以此来保证树的平衡。

5. 验证二叉搜索树 (LeetCode 98):

   • 利用递归和范围限制（最小值和最大值）来确保所有的节点符合二叉搜索树的性质。

6. 二叉搜索树中第K小的元素 (LeetCode 230):

   • 通过中序遍历来访问节点，因为中序遍历二叉搜索树会按照元素的升序进行。

这篇关于2024.06.21 刷题日记的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---