73
/ 100
分享面试经常出现的算法题和解法。第一部分见：字节面试高频百题(一)
21、按之字形顺序打印二叉树
牛客 14 按之字形顺序打印二叉树
-
https://www.nowcoder.com/practice/91b69814117f4e8097390d107d2efbe0?tpId=117&tqId=37722
思路：
-
借助队列的层序遍历+偶数层翻转结果
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
public ArrayList<ArrayList<Integer>> Print (TreeNode pRoot) {
if(pRoot == null) return res;
// write code here
traverse(pRoot);
return res;
}
public void traverse(TreeNode root) {
if(root == null) return;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int level = 0;
while (!queue.isEmpty()) {
level++;
int curLevelSize = queue.size();
ArrayList<Integer> curLevelValList = new ArrayList<>();
for (int i = 0; i < curLevelSize; i++) {
TreeNode curNode = queue.poll();
curLevelValList.add(curNode.val);
//遍历当前队列中节点，即当前层节点，把子节点加入队列
if (curNode.left != null) {
queue.offer(curNode.left);
}
if (curNode.right != null) {
queue.offer(curNode.right);
}
}
if(level%2==0) Collections.reverse(curLevelValList);
res.add(curLevelValList);
}
}
22、两个链表生成相加链表
牛客 40 链表相加：
-
https://www.nowcoder.com/practice/c56f6c70fb3f4849bc56e33ff2a50b6b?tpId=117
思路：
-
链表反转+进位控制
public ListNode addInList (ListNode head1, ListNode head2) {
//任意一个链表为空，返回另一个
if (head1 == null) return head2;
if (head2 == null) return head1;
//反转两个链表
head1 = reverse(head1);
head2 = reverse(head2);
//添加表头
ListNode dummy = new ListNode(-1);
ListNode p = dummy;
//进位符号
int carry = 0;
while (head1 != null || head2 != null || carry != 0) {
//链表不为空则取其值
int val1 = head1 == null ? 0 : head1.val;
int val2 = head2 == null ? 0 : head2.val;
int temp = val1 + val2 + carry;
//获取进位
carry = temp / 10;
temp %= 10;
//添加元素
p.next = new ListNode(temp);
p = p.next;
//移动下一个
if (head1 != null) head1 = head1.next;
if (head2 != null) head2 = head2.next;
}
return reverse(dummy.next);
}
private ListNode reverse(ListNode head) {
if (head == null) return null;
ListNode cur = head, pre = null;
while (cur != null) {
//记录 cur.next 用于更新 pre
ListNode next = cur.next;
//反转当前节点和前一个节点的指针方向
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
23、二叉树的最近公共祖先
力扣 236 二叉树的最近公共祖先：
-
https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/description/
思路：
-
后序位置处理 -
函数定义：返回以 root 为根，p和q的最近公共祖先 -
情况1：p、q都在root树里，返回就是p、q的最近公共祖先 -
情况2：p、q都不在root树里，返回null -
情况3：p、q有一个在root树里，返回p或者q
-
//函数定义：返回以 root 为根，p和q的最近公共祖先
//情况1：p、q都在root树里，返回就是p、q的最近公共祖先
//情况2：p、q都不在root树里，返回null
//情况3：p、q有一个在root树里，返回p或者q
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//base case
if(root == null) return null;
if(root == p || root == q) return root;
//状态转移，root 为变量
TreeNode left = lowestCommonAncestor(root.left,p,q);
TreeNode right = lowestCommonAncestor(root.right,p,q);
//后序位置写核心逻辑
//pq都在当前子树
if(left != null && right != null) return root;
//pq都不在当前子树
if(left == null && right == null) return null;
//p或q有一个在当前子树
return left != null? left:right;
}
24、螺旋矩阵
力扣 54 /牛客 38 螺旋矩阵
-
https://leetcode.cn/problems/spiral-matrix/description/ -
https://www.nowcoder.com/practice/7edf70f2d29c4b599693dc3aaeea1d31?tpId=117
思路：
-
四个方向边界控制移动范围
public ArrayList<Integer> spiralOrder (int[][] matrix) {
ArrayList<Integer> res = new ArrayList<>();
if(matrix.length == 0){
return res;
}
int m = matrix.length, n = matrix[0].length;
//初始化四个方向的边界值
int upperBound = 0, lowerBound = m - 1;
int leftBound = 0, rightBound = n - 1;
// res.size() == m * n 则遍历完整个数组
while (res.size() < m * n) {
//上下边界合法
if (upperBound <= lowerBound) {
//在顶部从左向右遍历
for (int i = leftBound; i <= rightBound; i++) {
res.add(matrix[upperBound][i]);
}
//遍历完上边界下移
upperBound++;
}
//左右边界合法
if(leftBound <= rightBound){
//在右侧从上到下遍历
for(int i = upperBound;i <=lowerBound;i++){
res.add(matrix[i][rightBound]);
}
rightBound--;
}
//上下边界合法
if (upperBound <= lowerBound) {
//在底部从右向左遍历
for (int i = rightBound; i >= leftBound; i--) {
res.add(matrix[lowerBound][i]);
}
lowerBound--;
}
//左右边界合法
if (leftBound <= rightBound){
//在左侧从下向上遍历
for (int i = lowerBound; i >= upperBound; i--) {
res.add(matrix[i][leftBound]);
}
leftBound++;
}
}
return res;
}
25、斐波那契
牛客 65 斐波那契：
-
https://www.nowcoder.com/practice/c6c7742f5ba7442aada113136ddea0c3?tpId=117
思路：
-
带备忘录的递归
int[] memo = new int[50];
public int Fibonacci (int n) {
Arrays.fill(memo, -1);
memo[1] = 1;
memo[2] = 1;
return fib(n);
}
public int fib (int n) {
if (memo[n] != -1) return memo[n];
if (n == 1 || n == 2) return 1;
int res = fib(n - 1) + fib(n - 2);
memo[n] = res;
return res;
}
26、最长回文子串
牛客17 最长回文子串
-
https://www.nowcoder.com/practice/b4525d1d84934cf280439aeecc36f4af?tpId=117
思路：
-
拆解成单字符为中心的回文串和双字符为中心的回文串求最长 -
回文串判定从中间向两边延伸，字符不等的时候取到最长回文串
public int getLongestPalindrome (String s) {
//以s[i]为中心的最长回文子串和以s[i]、s[i-1]为中心的最长回文子串求大的值
String res = "";
for (int i = 0; i < s.length(); i++) {
// 以s[i]为中心的最长回文子
String s1 = palindrome(s, i, i);
// 以s[i]和s[i+1]为中心的最长回文子串
String s2 = palindrome(s, i, i + 1);
//res = longest(res, s1, s2)
res = res.length() > s1.length() ? res : s1;
res = res.length() > s2.length() ? res : s2;
}
return res.length();
}
//找到指定索引范围内的回文串（向两边延伸）
private String palindrome(String s, int left, int right) {
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
left--;
right++;
}
// 不符合回文的时候返回以 s[left] 和 s[right] 为中心的最长回文串
return s.substring(left + 1, right);
}
27、三数之和
力扣 15 /牛客 54 三数之和：
-
https://leetcode.cn/problems/3sum/description/ -
https://www.nowcoder.com/practice/345e2ed5f81d4017bbb8cc6055b0b711?tpId=188
思路：
-
nSum问题，可以通过 twoSum 方法延伸。
public ArrayList<ArrayList<Integer>> threeSum (int[] num) {
// 两数之和用前后指针相向而行锁定，三数则为 当前元素+和为(0 - 当前元素)的元素集合
//排序
Arrays.sort(num);
ArrayList<ArrayList<Integer>> threeSumRes = new ArrayList<>();
//穷举 threeSum 的第一个数
for (int i = 0; i < num.length; i++) {
//对 target - nums[i] 计算 twoSum
ArrayList<ArrayList<Integer>> twoSumRes = twoSum(num, i + 1, 0 - num[i]);
//如果存在满足条件的二元组，再加上 nums[i]就是结果三元组。排序是因为结果要求升序
for (ArrayList<Integer> twoSumSingleRes : twoSumRes) {
//放入当前值
twoSumSingleRes.add(num[i]);
Collections.sort(twoSumSingleRes);
threeSumRes.add(twoSumSingleRes);
}
//跳过第一个数字重复的情况，否则会出现重复结果
while (i < num.length - 1 && num[i] == num[i + 1]) i++;
}
return threeSumRes;
}
private ArrayList<ArrayList<Integer>> twoSum(int[] num, int start, int target) {
ArrayList<ArrayList<Integer>> towSumRes = new ArrayList<>();
if (start < 0 || start >= num.length) return towSumRes;
int lo = start, hi = num.length - 1;
while (lo < hi) {
//记录lo和hi最初的值
int left = num[lo], right = num[hi];
if (num[lo] + num[hi] < target) {
while (lo < hi && num[lo] == left) lo++;
} else if (num[lo] + num[hi] > target) {
while (lo < hi && num[hi] == right) hi--;
} else if (num[lo] + num[hi] == target) {
ArrayList<Integer> twoSumSingleRes = new ArrayList();
twoSumSingleRes.add(num[lo]);
twoSumSingleRes.add(num[hi]);
towSumRes.add(twoSumSingleRes);
//跳过重复元素
while (lo < hi && num[lo] == left) lo++;
while (lo < hi && num[hi] == right) hi--;
}
}
return towSumRes;
}
28、重建二叉树
牛客 12 重建二叉树：
-
https://www.nowcoder.com/practice/8a19cbe657394eeaac2f6ea9b0f6fcf6?tpId=117
思路：
-
画出前序和中序根、左子树、右子树的关系图 -
根节点在前序第一位，拿到根节点的值，可以锁定中序中根节点的索引 -
根据中序根节点索引，能锁定左子树的大小 -
进而锁定左右子树构建范围
-
//存储 inorder 中值到索引的映射
HashMap<Integer, Integer> val2Index = new HashMap<>();
public TreeNode reConstructBinaryTree (int[] preOrder, int[] vinOrder) {
for (int i = 0; i < vinOrder.length; i++) {
val2Index.put(vinOrder[i], i);
}
//前序锁定根节点的值，找到中序数组根节点位置，确定左子树大小
return buildTree(preOrder, 0, preOrder.length - 1, vinOrder, 0,
vinOrder.length - 1);
}
//前序数组 preOder[preStart..preEnd]，中序 inOrder[inStart..inEnd]
public TreeNode buildTree (int[] preOrder, int preStart, int preEnd,
int[] inOrder, int inStart, int inEnd) {
if(preStart > preEnd || inStart>inEnd) return null;
//root 节点对应值为前序第一个元素
int rootVal = preOrder[preStart];
//构造当前根节点
TreeNode root = new TreeNode(rootVal);
// rootVal 在中序数组中的索引
int inRootIndex = val2Index.get(rootVal);
int leftSize = inRootIndex - inStart;
int leftPreStart = preStart + 1, leftPreEnd = preStart + leftSize;
int leftInStart = inStart, leftInEnd = inStart + leftSize - 1;
TreeNode leftNode = buildTree(preOrder, leftPreStart, leftPreEnd, inOrder,
leftInStart, leftInEnd);
int rightPreStart = leftPreEnd + 1, rightPreEnd = preEnd;
int rightInStart = inRootIndex + 1, rightInEnd = inEnd;
TreeNode rightNode = buildTree(preOrder, rightPreStart, rightPreEnd, inOrder,
rightInStart, rightInEnd);
root.left = leftNode;
root.right = rightNode;
return root;
}
29、求平方根
力扣 69/牛客 32 求平方根：
-
https://leetcode.cn/problems/sqrtx/description/ -
https://www.nowcoder.com/practice/09fbfb16140b40499951f55113f2166c?tpId=117
思路：
-
时间复杂度O(logx)，用二分法
public int mySqrt(int x) {
// 特殊值判断
if (x == 0) return 0;
if (x == 1) return 1;
int left = 1;
int right = x / 2;
// 在区间 [left..right] 查找目标元素
while (left < right) {
int mid = left + (right - left + 1) / 2;
// 注意：这里为了避免乘法溢出，改用除法
if (mid > x / mid) {
// 下一轮搜索区间是 [left..mid - 1]
right = mid - 1;
} else if (mid == x / mid) {
// 由于本题特殊性，如果 mid == x / mid 就找到了答案，其它问题不一定可以这样
return mid;
} else {
// 下一轮搜索区间是 [mid..right]
left = mid;
}
}
return left;
}
30、在旋转过的有序数组中寻找目标值
牛客 48 在旋转过的有序数组中寻找目标值：
-
https://www.nowcoder.com/practice/87c0e7abcbda41e7963660fa7d020995?tpId=117
思路：
-
找到k，分别在两侧左二分查找
public int search (int[] nums, int target) {
// write code here
//找到k,分别在 nums[0..k-1] 和 nums[k..n-1]做二分查找
if (nums.length == 0) return -1;
int k = 0;
boolean isReverse = false;
for (int i = 1; i < nums.length; i++) {
if (nums[i] < nums[i - 1]) {
k = i;
isReverse = true;
continue;
}
}
if (!isReverse) return binarySearch(nums, 0, nums.length - 1, target);
if (k == 0) return nums[k] == target ? k : -1;
int leftRes = binarySearch(nums, 0, k - 1, target);
int rightRes = binarySearch(nums, k, nums.length - 1, target);
return leftRes != -1 ? leftRes : rightRes;
}
private int binarySearch(int[] nums, int left, int right, int target) {
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] == target) {
return mid;
}
}
return -1;
}
31、包含min函数的栈
牛客 90 包含min函数的栈：
-
https://www.nowcoder.com/practice/4c776177d2c04c2494f2555c9fcc1e49?tpId=117
思路：
-
构建最小值的栈
public class Solution {
private Stack<Integer> stack = new Stack<>();
private Stack<Integer> minStack = new Stack<>();
public void push(int node) {
stack.push(node);
//最小值入栈
if (minStack.isEmpty() || minStack.peek() >= node) {
minStack.push(node);
}
}
public void pop() {
if (!stack.isEmpty()) {
int top = stack.pop();
//出栈的值小，要更新最小值
if (!minStack.isEmpty() && top <= minStack.peek()) {
minStack.pop();
}
}
}
public int top() {
return stack.peek();
}
public int min() {
return minStack.peek();
}
}
32、合并K个升序链表
力扣 23/牛客 51 合并K个升序链表：
-
https://leetcode.cn/problems/merge-k-sorted-lists/description/ -
https://www.nowcoder.com/practice/65cfde9e5b9b4cf2b6bafa5f3ef33fa6?tpId=117
思路：
-
优先级队列
public ListNode mergeKLists (ArrayList<ListNode> lists) {
if (lists == null || lists.size() == 0) return null;
// 虚拟头节点，连接合并后的链表
ListNode dummy = new ListNode(-1);
// 优先级队列，最小堆
PriorityQueue<ListNode> pq = new PriorityQueue<>(lists.size(), (a,
b)->(a.val - b.val));
// 队列添加 k 个链表的头节点
for (ListNode head : lists) {
// 空节点处理
if (head != null)pq.offer(head);
}
// 游标指针p指向头节点
ListNode p = dummy;
//执行节点连接操作，从队列中取
while (!pq.isEmpty()) {
//最小节点
ListNode queueHead = pq.poll();
// 队头最小节点接到结果链表中
p.next = queueHead;
//出队节点的下一个节点入队
if (queueHead.next != null) {
pq.offer(queueHead.next);
}
// p 指针不断前进
p = p.next;
}
return dummy.next;
}
33、字符串的排列（全排列）
牛客 121 字符串的排列：
-
https://www.nowcoder.com/practice/fe6b651b66ae47d7acce78ffdd9a96c7?tpId=117
思路：
-
排序 & 回溯框架 & 剪枝
ArrayList<String> res = new ArrayList<>();
public ArrayList<String> Permutation (String str) {
if(str == null || str.length() == 0 ) return res;
char[] strArr = str.toCharArray();
//按字典序排序
Arrays.sort(strArr);
//记录「路径」
StringBuilder track = new StringBuilder();
//「路径」中的元素会被标记为 true，避免重复使用
boolean[] used = new boolean[str.length()];
backtrak(strArr, track, used);
return res;
}
//路径：记录在 track 中
//选择列表：strArr 中不存在与 track 的那些字符，used 为 false
//结束条件：strArr 中的元素全都在track中出现
private void backtrak(char[] strArr, StringBuilder track,
boolean[] used) {
//触发结束条件
if (strArr.length == track.length()) {
res.add(track.toString());
return;
}
for (int i = 0; i < strArr.length; i++) {
//strArr[i]已经在track中，跳过
if (used[i]) continue;
//当前元素str[i]与同一层前一个元素str[i-1]相同且str[i-1]已经用过
if (i > 0 && strArr[i] == strArr[i - 1] && used[i - 1]) continue;
//做选择
track.append(strArr[i]);
used[i] = true;
//进入下一层决策树
backtrak(strArr, track, used);
//取消选择
track.deleteCharAt(track.length() - 1);
used[i] = false;
}
}
34、数字字符串转化成IP地址(全排列)
力扣 93 复原IP地址：牛客 20 数字字符串转化成IP地址：
-
https://leetcode.cn/problems/restore-ip-addresses/description/ -
https://www.nowcoder.com/practice/ce73540d47374dbe85b3125f57727e1e?tpId=117
class Solution {
List<String> res = new LinkedList<>();
LinkedList<String> track = new LinkedList<>();
public List<String> restoreIpAddresses(String s) {
backtrack(s, 0);
return res;
}
// 回溯算法框架
void backtrack(String s, int start) {
if (start == s.length() && track.size() == 4) {
// base case，走到叶子节点
// 即整个 s 被成功分割为合法的四部分，记下答案
res.add(String.join(".", track));
}
for (int i = start; i < s.length(); i++) {
if (!isValid(s, start, i)) {
// s[start..i] 不是合法的 ip 数字，不能分割
continue;
}
if (track.size() >= 4) {
// 已经分解成 4 部分了，不能再分解了
break;
}
// s[start..i] 是一个合法的 ip 数字，可以进行分割
// 做选择，把 s[start..i] 放入路径列表中
track.addLast(s.substring(start, i + 1));
// 进入回溯树的下一层，继续切分 s[i+1..]
backtrack(s, i + 1);
// 撤销选择
track.removeLast();
}
}
// 判断 s[
boolean isValid(String s, int start, int end) {
int length = end - start + 1;
if (length == 0 || length > 3) {
return false;
}
if (length == 1) {
// 如果只有一位数字，肯定是合法的
return true;
}
if (s.charAt(start) == '0') {
// 多于一位数字，但开头是 0，肯定不合法
return false;
}
if (length <= 2) {
// 排除了开头是 0 的情况，那么如果是两位数，怎么着都是合法的
return true;
}
// 现在输入的一定是三位数
if (Integer.parseInt(s.substring(start, start + length)) > 255) {
// 不可能大于 255
return false;
} else {
return true;
}
}
}
35、集合的所有子集(全排列)
力扣 78/牛客 27 集合中所有子集：
-
https://www.nowcoder.com/practice/c333d551eb6243e0b4d92e37a06fbfc9?tpId=117 -
https://leetcode.cn/problems/subsets/description/
//定义二维数组res用于存储结果
List<List<Integer>> res = new LinkedList<>();
public List<List<Integer>> subsets(int[] nums) {
//定义路径数组
List<Integer> track = new LinkedList<>();
backtrack(nums, 0, track);
return res;
}
public void backtrack(int[] nums, int start, List<Integer> track) {
//添加路径数组到结果数组中
res.add(new LinkedList<>(track));
//for循环遍历数组nums
for (int i = start; i < nums.length; i++) {
//做选择，将选择添加到路径数组中
track.add(nums[i]);
//回溯，继续向后遍历
backtrack(nums, i + 1, track);
//撤销选择，将选择从路径中删除
track.remove(track.size() - 1);
}
}
36、没有重复项数字(全排列)
力扣 46 全排列
牛客 43 没有重复项数字的全排列
-
https://leetcode.cn/problems/permutations/description/ -
https://www.nowcoder.com/practice/4bcf3081067a4d028f95acee3ddcd2b1?tpId=117
List<List<Integer>> res = new LinkedList<>();
/* 主函数，输入一组不重复的数字，返回它们的全排列 */
List<List<Integer>> permute(int[] nums) {
// 记录「路径」
LinkedList<Integer> track = new LinkedList<>();
// 「路径」中的元素会被标记为 true，避免重复使用
boolean[] used = new boolean[nums.length];
backtrack(nums, track, used);
return res;
}
// 路径：记录在 track 中
// 选择列表：nums 中不存在于 track 的那些元素（used[i] 为 false）
// 结束条件：nums 中的元素全都在 track 中出现
void backtrack(int[] nums, LinkedList<Integer> track, boolean[] used) {
// 触发结束条件
if (track.size() == nums.length) {
res.add(new LinkedList(track));
return;
}
for (int i = 0; i < nums.length; i++) {
// 排除不合法的选择
if (used[i]) {
// nums[i] 已经在 track 中，跳过
continue;
}
// 做选择
track.add(nums[i]);
used[i] = true;
// 进入下一层决策树
backtrack(nums, track, used);
// 取消选择
track.removeLast();
used[i] = false;
}
}
37、有重复项数字(全排列)
力扣 47 全排列2：牛客 42 有重复项数字的全排列
-
https://leetcode.cn/problems/permutations-ii/description/ -
https://www.nowcoder.com/practice/a43a2b986ef34843ac4fdd9159b69863?tpId=117
思路：
-
回溯+剪枝
List<List<Integer>> res = new LinkedList<>();
LinkedList<Integer> track = new LinkedList<>();
boolean[] used;
public List<List<Integer>> permuteUnique(int[] nums) {
// 先排序，让相同的元素靠在一起
Arrays.sort(nums);
used = new boolean[nums.length];
backtrack(nums);
return res;
}
void backtrack(int[] nums) {
if (track.size() == nums.length) {
res.add(new LinkedList(track));
return;
}
for (int i = 0; i < nums.length; i++) {
if (used[i]) {
continue;
}
// 新添加的剪枝逻辑，固定相同的元素在排列中的相对位置
if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
continue;
}
track.add(nums[i]);
used[i] = true;
backtrack(nums);
track.removeLast();
used[i] = false;
}
}
38、输出二叉树的右视图
力扣 199/牛客 136 输出二叉树的右视图：
-
https://leetcode.cn/problems/binary-tree-right-side-view/ -
https://www.nowcoder.com/practice/c9480213597e45f4807880c763ddd5f0?tpId=117
思路：
-
前序中序构建树+层序遍历的变形
ArrayList<Integer> res = new ArrayList<>();
public List<Integer> rightSideView(TreeNode root) {
// 层序遍历变形，每一层的最后一个节点加到结果集
traverse(root);
return res;
}
// 层序遍历，构造一个队列存放当前层的节点
private void traverse(TreeNode root) {
if (root == null)
return;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
// 当前层队列的大小，用于遍历
int size = queue.size();
for (int i = 0; i < size; i++) {
// 遍历到的节点出队
TreeNode node = queue.poll();
// 【逻辑处理位置】走到当前层的最后一个节点，添加到当前层结果中
if (i == size - 1)
res.add(node.val);
// 如果有子节点，入队，作为下一层处理
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
}
}
39、岛屿数量
牛客 109 岛屿数量：
-
https://www.nowcoder.com/practice/0c9664d1554e466aa107d899418e814e?tpId=117
思路：
-
dfs，遇到岛屿加入结果，并用dfs把岛屿淹掉，即遇到1，就把周围的1变为0，
public int solve (char[][] grid) {
if (grid.length == 0) return 0;
int res = 0;
int m = grid.length, n = grid[0].length;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
//发现岛屿，结果集加一
if (grid[i][j] == '1') res++;
//dfs把岛屿淹掉
dfs(grid, i, j);
}
}
return res;
}
//从(i,j)开始，将与之相邻的陆地都变成还是
private void dfs(char[][] grid, int i, int j) {
int m = grid.length, n = grid[0].length;
if (i < 0 || i >= m || j < 0 || j >= n) return;
//如果已经是海水了，返回
if (grid[i][j] == '0') return;
//将(i,j)变成海水
grid[i][j] = '0';
//淹没上下左右的陆地
dfs(grid, i, j - 1);
dfs(grid, i, j + 1);
dfs(grid, i - 1, j);
dfs(grid, i + 1, j);
}
40、二叉树的最大深度
力扣 104/牛客13 二叉树的最大深度：
-
https://leetcode.cn/problems/maximum-depth-of-binary-tree/description/ -
https://www.nowcoder.com/practice/8a2b2bf6c19b4f23a9bdb9b233eefa73?tpId=117
public int maxDepth (TreeNode root) {
// 二叉树的最大深度为左子树的最大深度+1或者右子树的最大深度+1
if (root == null) return 0;
return Math.max(maxDepth(root.left) + 1, maxDepth(root.right) + 1);
}
回溯算法思路：
int depth = 0;
int res = 0;
public int maxDepth(TreeNode root) {
traverse(root);
return res;
}
// 遍历二叉树
void traverse(TreeNode root) {
if (root == null) {
return;
}
// 前序遍历位置
depth++;
// 遍历的过程中记录最大深度
res = Math.max(res, depth);
traverse(root.left);
traverse(root.right);
// 后序遍历位置
depth--;
}
我是蜗牛，大厂程序员，专注技术原创和个人成长，正在互联网上摸爬滚打。欢迎关注我，和蜗牛一起成长，我们一起牛~下期见！
推荐阅读：
1120页的Leetcode算法刷题笔记，完整版PDF开放下载！
更多内容请收藏：Java for You
