二叉树基本函数一、二叉树节点结构体#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: vectorvectorint 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: vectorint rightSideView(TreeNode* root) { vectorintter; queueTreeNode*q; q.push(root); if(!root) { return ter; } while(!q.empty()) { auto nodeq.front(); int curq.size(); for(int i1;icur;i) { ter.push_back(node-val); q.pop(); if(node-right) q.push(node-right); } } return ter; } }; //在此基础上修改过的代码取每层最后一个结点AC class Solution { public: vectorint rightSideView(TreeNode* root) { vectorint ans; if (!root) return ans; queueTreeNode* 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: vectordouble averageOfLevels(TreeNode* root) { vectordoubleans; vectorintmid;//简洁点的就是不用mid来储存每层的数可以直接每层用sum相加再归零反复 double p; double sum0; queueTreeNode*q; if(!root) return ans; q.push(root); while(!q.empty()) { //auto nodeq.front();这步放错位置了 int curlevelsizeq.size(); for(int i1;icurlevelsize;i) { auto nodeq.front();//结点不是每层更新是每步都要更新 mid.push_back(node-val); q.pop(); if(node-left) q.push(node-left); if(node-right) q.push(node-right); } for(int j0;j(int)mid.size();j) { summid[j]; } double kmid.size(); psum/k; sum0; ans.push_back(p); mid.clear(); } /*for(int i0;i(int)ans.size();i) { if(ians.size()-1) { coutfixedsetprecision(5)ans[i]; } else { coutfixedsetprecision(5)ans[i],; } }*/这步不需要double浮点数本就保留到五位小数 return ans; } };515. 在每个树行中找最大值fmax(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 例13 → 二进制 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、数组里存值、构造对象pairint,int p {1,2}; vectorint v {3,4,5}; q.push({node, remain});2. 什么时候用 中括号[]结构化绑定解构 pair/tuple只在 C17 支持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; } } };未完待续。