网站免费源码不用下载,网站建设自身优势的分析,游戏币网站建设成本,做外贸需要关注的网站有什么问题系列综述#xff1a; #x1f49e;目的#xff1a;本系列是个人整理为了秋招面试的#xff0c;整理期间苛求每个知识点#xff0c;平衡理解简易度与深入程度。 #x1f970;来源#xff1a;材料主要源于【CodeTopHot200】进行的#xff0c;每个知识点的修正和深入主要参… 系列综述 目的本系列是个人整理为了秋招面试的整理期间苛求每个知识点平衡理解简易度与深入程度。 来源材料主要源于【CodeTopHot200】进行的每个知识点的修正和深入主要参考各平台大佬的文章其中也可能含有少量的个人实验自证所有代码均优先参考最佳性能。 结语如果有帮到你的地方就点个赞和关注一下呗谢谢 【C】秋招实习面经汇总篇 文章目录 基础知识二叉树广度优先遍历*递归算法非递归算法 相关题目199. 二叉树的右视图104. 二叉树的最大深度111. 二叉树的最小深度求二叉树最左下的叶子 参考博客 点此到文末惊喜↩︎
基础知识
二叉树广度优先遍历*
递归算法
非重点// 递归参数如果需要修改要进行引用传递
void traversal(TreeNode* cur, vectorvectorint result, int depth) {// 递归出口if (cur nullptr) return;// 递归体if (result.size() depth) // 扩容result.push_back(vectorint());// 原地构建数组result[depth].push_back(cur-val);// 顺序压入对应深度的数组中order(cur-left, result, depth 1);order(cur-right, result, depth 1);
}
vectorvectorint levelOrder(TreeNode* root) {// 初始化一般为递归形参vectorvectorint result;int depth 0;// 递归调用traversal(root, result, depth);// 返回结果return result;
}非递归算法
重点vectorvectorint levelOrder(TreeNode* root) {vectorvectorint res; // 结果容器queueTreeNode* que; // 队列if (root ! nullptr) que.push(root);// 根非空入队while (!que.empty()) {vectorint vec; // 每层结果int size que.size(); // 记录当前层结点数量for (int i 0; i size; i) {// 先记录后修改TreeNode *node que.front();que.pop();// 按序压入每个结点的左右孩子if (node-left) que.push(node-left);if (node-right) que.push(node-right);// 每个结点的处理vec.push_back(node-val);}// 每层结点的处理res.emplace_back(vec);} return res;
}相关题目
199. 二叉树的右视图
题目 给定一个二叉树的 根节点 root想象自己站在它的右侧按照从顶部到底部的顺序返回从右侧所能看到的节点值。
vectorint rightSideView(TreeNode* root) {queueTreeNode* que;if (root ! NULL) que.push(root);vectorint result;while (!que.empty()) {int size que.size();for (int i 0; i size; i) {TreeNode* node que.front();que.pop();// 将每一层的最后元素放入result数组中if (i (size - 1)) result.push_back(node-val);if (node-left) que.push(node-left);if (node-right) que.push(node-right);}}return result;
}104. 二叉树的最大深度
题目 给定一个二叉树 root 返回其最大深度。二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
// 递归方式(后序遍历的应用模板)
int maxDepth(TreeNode* root) {auto self [](auto self, TreeNode *root)-int{if (root nullptr) return 0;int max_left self(self, root-left);int max_right self(self, root-right);return max(max_left, max_right) 1;};return self(self, root);
}// 非递归方式
int maxDepth(TreeNode *root) {int depth 0; // 结果queueTreeNode* que; // 队列if (root ! nullptr)que.push(root);while (!que.empty()) {// 层次遍历int size que.size();for (int i 0; i size; i) {TreeNode *node que.front();que.pop();if (node-left) que.push(node-left);if (node-right) que.push(node-right);}// 层数1depth;} return depth;
}111. 二叉树的最小深度
核心思路 层次遍历中一直记录深度。直到返回第一个左右孩子均为空时的depth 递归法 分别对二叉树的五种形态进行讨论 int minDepth(TreeNode* root) {// 空二叉树if (root NULL) return 0;// 只有左子树if (root-left ! NULL root-right NULL) {return 1 minDepth(root-left);}// 只有右子树if (root-left NULL root-right ! NULL) {return 1 minDepth(root-right);}// 左右子树都非空return 1 min(minDepth(root-left), minDepth(root-right));
}非递归法 层次遍历中找到第一个左右孩子均为空的即为最小深度 int minDepth(TreeNode* root) {if (root NULL) return 0;int depth 0;queueTreeNode* que;que.push(root);while(!que.empty()) {int size que.size();depth; // 记录最小深度for (int i 0; i size; i) {TreeNode* node que.front();que.pop();if (!node-left !node-right) { // 第一个左右孩子均空为最小深度return depth;if (node-left) que.push(node-left);if (node-right) que.push(node-right);}}}return depth;
}求二叉树最左下的叶子
题目 给定一个二叉树的 根节点 root请找出该二叉树的 最底层 最左边 节点的值。 思路 使用层次遍历每次记录第一个结点的值最后就是最左下的结点
int findBottomLeftValue(TreeNode* root) {TreeNode *res nullptr;queueTreeNode* que;if (root ! nullptr) que.push(root);while (!que.empty()) {int size que.size();for (int i 0; i size; i) {TreeNode *node que.front();que.pop();if (i 0) res node; // 每次记录第一个结点if (node-left) que.push(node-left);if (node-right) que.push(node-right);}}return res-val;}少年我观你骨骼清奇颖悟绝伦必成人中龙凤。 不如点赞·收藏·关注一波 点此跳转到首行↩︎
参考博客 「代码随想录」47. 全排列 II:【彻底理解排列中的去重问题】详解 codetop
