面试资料

岛屿数量给你一个由 '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",& ...

二叉树中的最大路径和二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。 路径和 是路径中各节点值的总和。 给你一个二叉树的根节点 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的最大路径和等于左子树的最大路径和+右子树的最大路径和+根节点的值。 如果某个节点的最大路径和是负数，那么就不加这个节点对应的子树，也就是返回 ...

二叉树的最近公共祖先如果当前节点是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); ...

路径总和 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。 否则：递归调用左子树和右子树 ...

从前序与中序遍历序列构造二叉树给定两个整数数组 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 ...

二叉树展开为链表给你二叉树的根结点 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 ...

二叉树的右视图给定一个二叉树的 根节点 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小的元素给定一个二叉搜索树的根节点 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 ...

将有序数组转换为二叉搜索树给你一个整数数组 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 ...

二叉树的直径给你一棵二叉树的根节点，返回该树的 直径 。 二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 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 ...