avatar
文章
169
标签
38
分类
4

首页
归档
标签
分类
面试资料
首页
归档
标签
分类

面试资料

岛屿数量
发表于2025-01-30|算法leetcode
岛屿数量给你一个由 '1'(陆地)和 '0'(水)组成的的二维网格,请你计算网格中岛屿的数量。 岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。 此外,你可以假设该网格的四条边均被水包围。 示例 1: 1234567输入:grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"]]输出:1 示例 2: 1234567输入:grid = [ ["1",& ...
二叉树中的最大路径和
发表于2025-01-29|算法leetcode
二叉树中的最大路径和二叉树中的 路径 被定义为一条节点序列,序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点,且不一定经过根节点。 路径和 是路径中各节点值的总和。 给你一个二叉树的根节点 root ,返回其 最大路径和 。 示例 1: 123输入:root = [1,2,3]输出:6解释:最优路径是 2 -> 1 -> 3 ,路径和为 2 + 1 + 3 = 6 示例 2: 123输入:root = [-10,9,20,null,null,15,7]输出:42解释:最优路径是 15 -> 20 -> 7 ,路径和为 15 + 20 + 7 = 42 提示: 树中节点数目范围是 [1, 3 * 104] -1000 <= Node.val <= 1000 二叉树的最大路径和等于以所有节点为拐点的最大路径和。 以图1为例子,当前根节点为1,1的最大路径和等于左子树的最大路径和+右子树的最大路径和+根节点的值。 如果某个节点的最大路径和是负数,那么就不加这个节点对应的子树,也就是返回 ...
二叉树的最近公共祖先
发表于2025-01-29|算法leetcode
二叉树的最近公共祖先如果当前节点是p(或q),最近公共祖先就是当前节点(或q) 如果当前节点是null,最近公共祖先就是null 如果当前节点的左子树的公共祖先节点不为空并且右子树不为空,那么当前节点为最近公共祖先 如果当前节点左子树返回空,说明左子树中没有p和q去右子树找,右边同理 12345678910111213141516class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if (root == null || root == q || root == p) { return root; } TreeNode left = lowestCommonAncestor(root.left, p, q); TreeNode right = lowestCommonAncestor(root.right, p, q); ...
路径总和 |||
发表于2025-01-29|算法leetcode
路径总和 III给定一个二叉树的根节点 root ,和一个整数 targetSum ,求该二叉树里节点值之和等于 targetSum 的 路径 的数目。 路径 不需要从根节点开始,也不需要在叶子节点结束,但是路径方向必须是向下的(只能从父节点到子节点)。 示例 1: 123输入:root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8输出:3解释:和等于 8 的路径有 3 条,如图所示。 示例 2: 12输入:root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22输出:3 提示: 二叉树的节点个数的范围是 [0,1000] -109 <= Node.val <= 109 -1000 <= targetSum <= 1000 因为不需要从根节点开始,所以需要对每一个节点进行求最大路径操作。 使用深搜,递归函数返回值是以该节点为根的树的路径总和为target的个数。 返回条件是如果遍历到空节点,返回0。 否则:递归调用左子树和右子树 ...
从前序与中序遍历序列构造二叉树
发表于2025-01-28|算法leetcode
从前序与中序遍历序列构造二叉树给定两个整数数组 preorder 和 inorder ,其中 preorder 是二叉树的先序遍历, inorder 是同一棵树的中序遍历,请构造二叉树并返回其根节点。 示例 1: 12输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]输出: [3,9,20,null,null,15,7] 示例 2: 12输入: preorder = [-1], inorder = [-1]输出: [-1] 提示: 1 <= preorder.length <= 3000 inorder.length == preorder.length -3000 <= preorder[i], inorder[i] <= 3000 preorder 和 inorder 均 无重复 元素 inorder 均出现在 preorder preorder 保证 为二叉树的前序遍历序列 inorder 保证 为二叉树的中序遍历序列 12345678910111213141516171819202122 ...
二叉树展开为链表
发表于2025-01-28|算法leetcode
二叉树展开为链表给你二叉树的根结点 root ,请你将它展开为一个单链表: 展开后的单链表应该同样使用 TreeNode ,其中 right 子指针指向链表中下一个结点,而左子指针始终为 null 。 展开后的单链表应该与二叉树 先序遍历 顺序相同。 示例 1: 12输入:root = [1,2,5,3,4,null,6]输出:[1,null,2,null,3,null,4,null,5,null,6] 示例 2: 12输入:root = []输出:[] 示例 3: 12输入:root = [0]输出:[0] 提示: 树中结点数在范围 [0, 2000] 内 -100 <= Node.val <= 100 进阶:你可以使用原地算法(O(1) 额外空间)展开这棵树吗? 先序遍历的顺序是根 左 右,所以很显然操作方法是把左子树都插到右边来。 具体的步骤为: 沿着右子树遍历二叉树 如果当前节点有左子树,找到这棵左子树的最右边的节点。 将左子树根节点一直到右子树的最右这条链插入当前节点后面 1234567891011121314151617class Sol ...
二叉树的右视图
发表于2025-01-28|算法leetcode
二叉树的右视图给定一个二叉树的 根节点 root,想象自己站在它的右侧,按照从顶部到底部的顺序,返回从右侧所能看到的节点值。 示例 1: 输入:root = [1,2,3,null,5,null,4] 输出:[1,3,4] 解释: 示例 2: 输入:root = [1,2,3,4,null,null,null,5] 输出:[1,3,4,5] 解释: 示例 3: 输入:root = [1,null,3] 输出:[1,3] 示例 4: 输入:root = [] 输出:[] 提示: 二叉树的节点个数的范围是 [0,100] -100 <= Node.val <= 100 使用中序遍历,将每一层最右边节点的值加入答案 12345678910111213141516171819202122232425262728293031class Solution { private static int max = 102; private List<Integer> list = new ArrayList& ...
二叉搜索树中第K小的元素
发表于2025-01-28|算法leetcode
二叉搜索树中第K小的元素给定一个二叉搜索树的根节点 root ,和一个整数 k ,请你设计一个算法查找其中第 k 小的元素(从 1 开始计数)。 示例 1: 12输入:root = [3,1,4,null,2], k = 1输出:1 示例 2: 12输入:root = [5,3,6,2,4,null,null,1], k = 3输出:3 提示: 树中的节点数为 n 。 1 <= k <= n <= 104 0 <= Node.val <= 104 进阶:如果二叉搜索树经常被修改(插入/删除操作)并且你需要频繁地查找第 k 小的值,你将如何优化算法? 因为二叉搜索树的中序遍历是有序的,所以使用中序遍历处理。 12345678910111213141516171819202122class Solution { int max = 10010; TreeNode[] stack = new TreeNode[max]; int top = 0; public int kthSmallest(TreeNo ...
将有序数组转换为二叉搜索树
发表于2025-01-27|算法leetcode
将有序数组转换为二叉搜索树给你一个整数数组 nums ,其中元素已经按 升序 排列,请你将其转换为一棵 平衡 二叉搜索树。 示例 1: 123输入:nums = [-10,-3,0,5,9]输出:[0,-3,9,-10,null,5]解释:[0,-10,5,null,-3,null,9] 也将被视为正确答案: 示例 2: 123输入:nums = [1,3]输出:[3,1]解释:[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。 提示: 1 <= nums.length <= 104 -104 <= nums[i] <= 104 nums 按 严格递增 顺序排列 为了保持树的平衡,每次选取区间的中点作为根节点。 建树的过程是一个递归方法,返回结果是树的根节点,结束条件是左边界超过右边界。根的左孩子等于递归建立根的左孩子,根的右孩子等于递归建立根的右孩子。 12345678910111213141516class Solution { public TreeNode sortedArrayToBST(int[] num ...
二叉树的直径
发表于2025-01-27|算法leetcode
二叉树的直径给你一棵二叉树的根节点,返回该树的 直径 。 二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。 两节点之间路径的 长度 由它们之间边数表示。 示例 1: 123输入:root = [1,2,3,4,5]输出:3解释:3 ,取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。 示例 2: 12输入:root = [1,2]输出:1 提示: 树中节点数目在范围 [1, 104] 内 -100 <= Node.val <= 100 二叉树的直径就是以某个节点作为根节点,左子树最大路径和+右子树最大路径和。使用深搜遍历每个节点,算出最大值 12345678910111213141516class Solution { private int ans; public int diameterOfBinaryTree(TreeNode root) { dfs(root); return ans; } private ...
1…567…17
avatar
范小勤
文章
169
标签
38
分类
4
Follow Me
公告
This is my Blog
最新文章
验证二叉搜索树2025-02-26
寻找重复数2025-02-17
下一个排列2025-02-17
颜色分类2025-02-16
只出现一次的数字2025-02-16
分类
  • 八股文11
  • 算法155
    • acwing22
    • leetcode133
标签
区间和 Trie 二叉树 模拟 完全背包 DFS 位运算 BFS 链表 优先队列 二叉搜索树 拓扑排序 哈希 01背包 栈 双向链表 差分 图论 摩尔投票 双指针 贪心 单调队列 桶排序 kmp 滑动窗口 并查集 前缀积 矩阵 递归 归并排序 单调栈 高精度 记忆化搜索 集合 二分 前缀和 动态规划 快速排序
归档
  • 二月 202543
  • 一月 202554
  • 十二月 202414
  • 九月 20241
  • 四月 202418
  • 三月 202419
  • 二月 202420
网站资讯
文章数目 :
169
本站访客数 :
本站总访问量 :
最后更新时间 :
©2020 - 2025 By 范小勤
框架 Hexo|主题 Butterfly