字节面试高频百题(二)

分享面试经常出现的算法题和解法。

按之字形顺序打印二叉树：使用队列的层序遍历和偶数层翻转结果。

两个链表生成相加链表：链表反转和进位控制。

二叉树的最近公共祖先：后序位置处理，判断p和q的位置。

螺旋矩阵：四个方向边界控制移动范围。

斐波那契：带备忘录的递归实现。

最长回文子串：从中心向两边延伸求解。

三数之和：nSum问题，通过twoSum方法延伸。

重建二叉树：根据前序和中序遍历构建树。

求平方根：使用二分法，时间复杂度O(logx)。

在旋转过的有序数组中寻找目标值：找到旋转点后分别二分查找。

包含min函数的栈：构建最小值的栈。

合并K个升序链表：使用优先级队列。

字符串的排列：使用回溯和剪枝。

数字字符串转化成IP地址：使用回溯算法。

集合的所有子集：使用回溯算法生成所有子集。

没有重复项数字的全排列：使用回溯算法生成全排列。

有重复项数字的全排列：使用回溯和剪枝。

输出二叉树的右视图：层序遍历变形，记录每层最后一个节点。

岛屿数量：使用DFS淹没岛屿，统计数量。

二叉树的最大深度：递归计算左右子树的最大深度。