增值服务包括哪些内容,宁波seo推广开发,东莞市网络营销公司,做logo有哪些网站系列综述#xff1a; #x1f49e;目的#xff1a;本系列是个人整理为了秋招面试的#xff0c;整理期间苛求每个知识点#xff0c;平衡理解简易度与深入程度。 #x1f970;来源#xff1a;材料主要源于【CodeTopHot200】进行的#xff0c;每个知识点的修正和深入主要参… 系列综述 目的本系列是个人整理为了秋招面试的整理期间苛求每个知识点平衡理解简易度与深入程度。 来源材料主要源于【CodeTopHot200】进行的每个知识点的修正和深入主要参考各平台大佬的文章其中也可能含有少量的个人实验自证所有代码均优先参考最佳性能。 结语如果有帮到你的地方就点个赞和关注一下呗谢谢 【C】秋招实习面经汇总篇 文章目录 基础知识二叉树DFS基本算法递归算法非递归算法 相关题目236. 二叉树的最近公共祖先110. 判断平衡二叉树后序遍历的示例222. 求树中结点的数量226. 翻转二叉树101. 对称二叉树左叶子之和二叉树的所有路径带缓存的前序遍历符合总和的路径 参考博客 点此到文末惊喜↩︎
基础知识
二叉树DFS基本算法
递归算法
注意 左右子树不需要if (root-left/rihgt)因为递归出口已经判断了后序遍历有个好处可以先收集和处理孩子然后根节点再进行处理 // 前序遍历
void Traversal(TreeNode *root) {if (root nullptr) return ;Doing(root-val); // 中Traversal(root-left); // 左Traversal(root-right); // 右
}
// 中序遍历
void Traversal(TreeNode *root) {if (root nullptr) return ;Traversal(root-left); // 左Doing(root-val); // 中Traversal(root-right); // 右
}
// 后序遍历
void Traversal(TreeNode *root, vectorint vec) {if (root nullptr) return ;Traversal(root-left); // 左Traversal(root-right); // 右vec.emplace_back(root-val);// 中
}非递归算法
注意点vectorint preorderTraversal(TreeNode* root) {vectorint res; // 结果容器stackTreeNode* st; // 深度栈if(root ! nullptr) st.push(root); // 根非空则入栈// 遍历源容器while (!st.empty()) { // key:注意使用的全部结点都是node// 先记录TreeNode *node st.top();st.pop();// 后操作if (node ! nullptr) {// 压入允许为逆序注意根节点要后压入nullptrif (node-right) st.push(node-right); if (node-left) st.push(node-left); st.push(node);st.push(nullptr);} else {// 先记录node st.top();st.pop();// 后操作res.emplace_back(node-val);}}return res;
}相关题目
236. 二叉树的最近公共祖先
题目 给定一个二叉树, 找到该树中两个指定节点p和q的最近公共祖先。 复杂度分析 时间复杂度 O(N) 其中 N为二叉树节点数最差情况下需要递归遍历树的所有节点。空间复杂度 O(N) 最差情况下递归深度达到 N 思路 递归出口如果不是nullptr表示找到了后序遍历优先遍历左右子树并进行记录结点处理 如果左右子树都非空一定表示该结点为公共祖先结点如果有一个为空则向上传递非空的那个结点
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {// 递归出口返回标志不为空说明是祖先结点if (root p || root q || root nullptr) return root;// 后序遍历TreeNode *left lowestCommonAncestor(root-left, p, q);TreeNode *right lowestCommonAncestor(root-right, p, q);// 中间结点的处理// 左右都非空表示该节点为公共祖先结点 if (left ! nullptr right ! nullptr)return root;// 有一个为空表示if (left nullptr) return right;if (right nullptr) return left;return root;
}110. 判断平衡二叉树后序遍历的示例
递归法 给定一个二叉树判断它是否是高度平衡的二叉树。一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。 // 初始化ans为true最后看ans是否为false即可
int depth(TreeNode* root, bool ans) {if(!root) return 0;// 后序遍历int left1depth(root-left, ans);int right1depth(root-right, ans);if(abs(left-right) 1) ans false;// 对根结点的处理// 递归出口return max(left,right); // 返回树的高度
}
// 尾递归优化效率高
bool isBalanced(TreeNode* root) {if (root nulllptr) return true;return abs(depth(root-left) - depth(root-right)) 1 isBalanced(root-left) isBalanced(root-right);
}222. 求树中结点的数量
题目 给你一棵 完全二叉树 的根节点 root 求出该树的节点个数。 算法int getNodesNum(TreeNode* cur) {if (cur NULL) return 0;int leftNum getNodesNum(cur-left); // 左int rightNum getNodesNum(cur-right); // 右int treeNum leftNum rightNum 1; // 中return treeNum;
}226. 翻转二叉树
给你一棵二叉树的根节点 root 翻转这棵二叉树并返回其根节点。
TreeNode* invertTree(TreeNode* root) {auto self [](auto self, TreeNode *root){if (root nullptr) return ;self(self, root-left);self(self, root-right);swap(root-left, root-right);return ;};self(self, root);return root;
}101. 对称二叉树
题目 求一颗二叉树是否镜像对称 思路 根节点必定对称关键是左右两子树的对称左右两个孩子存在的情况下递归比较左右两颗子树的情况
bool isSymmetric(TreeNode* root) {auto self [](auto self, TreeNode *left, TreeNode *right)-bool{// 递归出口if (left nullptr right nullptr) return true;else if (left ! nullptr right nullptr) return false;else if (left nullptr right ! nullptr) return false;else if (left-val ! right-val) return false;// 后序遍历递归比较并汇总结果bool outside self(self, left-left, right-right);bool inside self(self,left-right, right-left);bool is_same outside inside;// 返回结果return is_same;};return self(self, root-left, root-right);
}左叶子之和
求二叉树的左叶子之和 遍历所有节点对所求的特殊节点进行约束求值 if (node-left ! nullptr node-left-left nullptr node-left-right nullptr)res node-left-val;二叉树的所有路径带缓存的前序遍历
递归 数字转化成字符串to_string(number)字符串后追加子串str.append(subStr)字符串删除某个位置之后的字符str.erase(position) // 数字型
void dfs(TreeNode*root,vectorintpath, vectorvectorint res) {if(!root) return; //根节点为空直接返回// 中path.push_back(root-val); //作出选择if(!root-left !root-right) //如果到叶节点 {res.push_back(path);return;}// 左dfs(root-left,path,res); //继续递归// 右dfs(root-right,path,res);
}
// 字符型
void binaryTree(TreeNode* root,string path,vectorstringres) {if(rootNULL) return ;path.append(to_string(root-val));path.append(-);if(root-leftNULLroot-rightNULL{path.erase(path.length()-2);res.push_back(path);}binaryTree(root-left,path,res);binaryTree(root-right,path,res);
}
vectorstring binaryTreePaths(TreeNode* root) {string path;vectorstringres;binaryTree(root,path,res);return res;
}符合总和的路径
题目 判断该树中是否存在 根节点到叶子节点 的路径这条路径上所有节点值相加等于目标和 targetSum 。如果存在返回 true否则返回 false // 递归方式前序遍历并记录每条路径的和
bool hasPathSum(TreeNode* root, int targetSum) {bool flag false;auto self [](auto self, TreeNode *root, int sum){// sum不可全局if (root nullptr) return ;// 根结点的处理sum root-val;cout sum ;if (root-left nullptr root-right nullptr targetSum sum) flag true;self(self, root-left, sum);self(self, root-right, sum);};self(self, root, 0);return flag;
}
// 非递归
bool hasPathSum(TreeNode* root, int targetSum) {// 初始化stackTreeNode* st;if(root ! nullptr) st.push(root);int sum 0;// 迭代while(!st.empty()){TreeNode *cur st.top();if(cur ! nullptr){st.pop();st.push(cur);st.push(nullptr);sum cur-val;if(cur-right) st.push(cur-right);if(cur-left) st.push(cur-left);}else{st.pop();cur st.top();st.pop();// 节点判断if(sum targetSum cur-left nullptr cur-right nullptr){return true;}else{// 回溯sum - cur-val;}}}return false;
}少年我观你骨骼清奇颖悟绝伦必成人中龙凤。 不如点赞·收藏·关注一波 点此跳转到首行↩︎
参考博客 「代码随想录」47. 全排列 II:【彻底理解排列中的去重问题】详解 codetop 力扣LeetCodeKrahets
