暑假日训【二叉树/链表】
二叉树基本函数
一、二叉树节点结构体
#include <bits/stdc++.h> using namespace std; // 二叉树结点定义 struct TreeNode { int val; // 节点值 TreeNode* left; // 左孩子 TreeNode* right; // 右孩子 // 构造函数 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} };二、1. 递归遍历（最常用）
前序遍历：根 → 左 → 右
void preOrder(TreeNode* root) { if (root == nullptr) return; cout << root->val << " "; preOrder(root->left); preOrder(root->right); }中序遍历：左 → 根 → 右（二叉搜索树升序）
void inOrder(TreeNode* root) { if (root == nullptr) return; inOrder(root->left); cout << root->val << " "; inOrder(root->right); }后序遍历：左 → 右 → 根
void postOrder(TreeNode* root) { if (root == nullptr) return; postOrder(root->left); postOrder(root->right); cout << root->val << " "; }三、2. 层序遍历（BFS 队列实现，按层打印）以题来举例
class Solution { public: vector<vector<int>> levelOrder(TreeNode* root) { vector <vector <int>> ret; if (!root) { return ret; } queue <TreeNode*> q; q.push(root); while (!q.empty()) { int currentLevelSize = q.size(); ret.push_back(vector <int> ()); for (int i = 1; i <= currentLevelSize; ++i) { auto node = q.front(); q.pop(); ret.back().push_back(node->val); if (node->left) q.push(node->left); if (node->right) q.push(node->right); } } return ret; } }; 作者：力扣官方题解 链接：https://leetcode.cn/problems/binary-tree-level-order-traversal/solutions/241885/er-cha-shu-de-ceng-xu-bian-li-by-leetcode-solution/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。199.二叉树的右视图
以以上的惯用思想不够，写了以下代码但有样例不对，哦哦只考虑到最右支了，是从右映射
/** * 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: vector<int> rightSideView(TreeNode* root) { vector<int>ter; queue<TreeNode*>q; q.push(root); if(!root) { return ter; } while(!q.empty()) { auto node=q.front(); int cur=q.size(); for(int i=1;i<=cur;++i) { ter.push_back(node->val); q.pop(); if(node->right) q.push(node->right); } } return ter; } }; //在此基础上修改过的代码，取每层最后一个结点，AC class Solution { public: vector<int> rightSideView(TreeNode* root) { vector<int> ans; if (!root) return ans; queue<TreeNode*> q; q.push(root); while (!q.empty()) { int sz = q.size(); // 当前层节点总数 // 遍历当前一整层 for (int i = 0; i < sz; i++) { auto node = q.front(); q.pop(); // 只要是当前层最后一个节点，就放进答案 if (i == sz - 1) { ans.push_back(node->val); } // 左右孩子入队，顺序无所谓 if (node->left) q.push(node->left); if (node->right) q.push(node->right); } } return ans; } };199. 二叉树的右视图 - 力扣（LeetCode）官方题解，他这个涉及的知识点也太多了，哈希表都用上了。
637. 二叉树的层平均值 以下是我一开始的思路，虽然通过了但不够简洁
class Solution { public: vector<double> averageOfLevels(TreeNode* root) { vector<double>ans; vector<int>mid;//简洁点的就是不用mid来储存每层的数可以直接每层用sum相加再归零反复 double p; double sum=0; queue<TreeNode*>q; if(!root) return ans; q.push(root); while(!q.empty()) { //auto node=q.front();这步放错位置了 int curlevelsize=q.size(); for(int i=1;i<=curlevelsize;++i) { auto node=q.front();//结点不是每层更新是每步都要更新 mid.push_back(node->val); q.pop(); if(node->left) q.push(node->left); if(node->right) q.push(node->right); } for(int j=0;j<(int)mid.size();++j) { sum+=mid[j]; } double k=mid.size(); p=sum/k; sum=0; ans.push_back(p); mid.clear(); } /*for(int i=0;i<(int)ans.size();++i) { if(i==ans.size()-1) { cout<<fixed<<setprecision(5)<<ans[i]; } else { cout<<fixed<<setprecision(5)<<ans[i]<<","; } }*/这步不需要，double浮点数本就保留到五位小数 return ans; } };515. 在每个树行中找最大值
f=max(node->val,f);我竟然在这道题中卡在了这一步！我竟然用一个 answer 来包含它的最大值，然后用 f 来代表它的下一个值。因为我想的是他下一个值在轮回来的时候，下一个值跟这个值做对比，最大的那一个。结果发生这个逻辑不对啊，应该是直接等于 f。
111. 二叉树的最小深度 以下这段代码可以判断叶子的所在层数
if (node->left == nullptr && node->right == nullptr) return depth;226. 翻转二叉树 基础代码
/** * 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: TreeNode* invertTree(TreeNode* root) { if(!root) return root; swap(root->left,root->right); invertTree(root->left); invertTree(root->right); return root; } };101. 对称二叉树
class Solution { public: bool check(TreeNode *p, TreeNode *q) { if (!p && !q) return true; if (!p || !q) return false; return p->val == q->val && check(p->left, q->right) && check(p->right, q->left); } bool isSymmetric(TreeNode* root) { return check(root->left, root->right); } };怎么今天把手放键盘上打代码却有了那些年弹钢琴的感觉。
222. 完全二叉树的节点个数 O(n)在这道题竟是算超时的，只有以下写法不超时O(log2n)
class Solution { public: int countNodes(TreeNode* root) { if (!root) return 0; // 求左树深度 int leftH = 0; TreeNode* l = root; while (l) { leftH++; l = l->left; } // 求右树深度 int rightH = 0; TreeNode* r = root; while (r) { rightH++; r = r->right; } if (leftH == rightH) { return (1 << leftH) - 1; //<< 是左移位运算符：1 << h = 2h 例：1<<3 → 二进制 1000 = 8 = 23 } return 1 + countNodes(root->left) + countNodes(root->right); } };110. 平衡二叉树
class Solution { public: // 辅助函数：计算一棵树的最大深度 int getDepth(TreeNode* node) { if (!node) return 0; return max(getDepth(node->left), getDepth(node->right)) + 1; } bool isBalanced(TreeNode* root) { // 1. 空树是平衡树 if (!root) return true; // 2. 计算当前节点左右子树高度 int leftDepth = getDepth(root->left); int rightDepth = getDepth(root->right); // 3. 当前高度差符合 且 左右子树都平衡 bool curOk = abs(leftDepth - rightDepth) <= 1; bool leftOk = isBalanced(root->left); bool rightOk = isBalanced(root->right); return curOk && leftOk && rightOk; } };106. 从中序与后序遍历序列构造二叉树 我觉得这个代码好复杂啊，提醒自己着重注意！
官方题解106. 从中序与后序遍历序列构造二叉树 - 力扣（LeetCode）
在做题中遇到个小细节
1. 什么时候用 大括号{}
- 往 pair、vector、数组里存值、构造对象
pair<int,int> p = {1,2}; vector<int> v = {3,4,5}; q.push({node, remain});2. 什么时候用 中括号[]
- 结构化绑定解构 pair/tuple（只在 C++17 支持）
auto [a, b] = pair变量;- 数组 /vector 下标取值（这个你肯定会）
vec[0], arr[1]236. 二叉树的最近公共祖先 我觉得这个题代码简单但递归逻辑强，从叶子往根推的感觉
class Solution { public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if (root == q || root == p || root == NULL) return root; TreeNode* left = lowestCommonAncestor(root->left, p, q); TreeNode* right = lowestCommonAncestor(root->right, p, q); if (left != NULL && right != NULL) return root; if (left == NULL && right != NULL) return right; else if (left != NULL && right == NULL) return left; else { // (left == NULL && right == NULL) return NULL; } } };未完待续。