字节面试高频百题(二)
原文中文，约18700字，阅读约需45分钟。
📝
内容提要
这篇文章介绍了常见的算法题和解法，包括按之字形顺序打印二叉树、两个链表生成相加链表、二叉树的最近公共祖先、螺旋矩阵、斐波那契、最长回文子串、三数之和、重建二叉树、求平方根、在旋转过的有序数组中寻找目标值、包含min函数的栈、合并K个升序链表、字符串的排列、数字字符串转化成IP地址、没有重复项数字的全排列、有重复项数字的全排列、输出二叉树的右视图、岛屿数量、二叉树的最大深度。
🔎
延伸解读
回溯算法在排列组合题中的核心应用
本文中字符串的排列、数字字符串转IP、子集、全排列等多道题均使用回溯算法。回溯框架通常包括路径记录、选择列表和结束条件，并通过剪枝避免重复。例如，有重复项的全排列需要先排序，再在递归时跳过同一层重复元素。掌握回溯模板能高效解决此类问题。
链表与二叉树题目的高频解法
链表相加通过反转链表和进位控制实现；二叉树的最近公共祖先利用后序遍历，根据左右子树返回值判断；重建二叉树则结合前序和中序的特性递归构建。这些题目考察对指针操作和递归思维的理解，是面试中的常见考点。
二分查找的变体与边界处理
求平方根和旋转数组查找目标值都运用了二分查找。求平方根需注意使用除法避免溢出，并处理特殊值；旋转数组则先找到旋转点，再在两侧分别二分。二分查找的难点在于边界条件的控制，如循环不变量和中间值计算。
❓
Q&A
如何按之字形顺序打印二叉树？
使用队列进行层序遍历，并在偶数层翻转结果。
如何将两个链表相加生成新的链表？
先反转两个链表，然后逐位相加并处理进位。
如何找到二叉树的最近公共祖先？
通过后序遍历判断p和q的位置，返回最近公共祖先。
螺旋矩阵的打印方法是什么？
通过四个方向的边界控制，逐层遍历矩阵。
如何求解斐波那契数列？
使用带备忘录的递归方法来避免重复计算。
如何计算字符串的最长回文子串？
从每个字符向两边扩展，判断回文长度并更新最大值。
🏷️
