Leetcode 17:电话号码的字母组合(最详细的解法!!!)

给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。 给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。 示例: 12输入:"23"输出:["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]. 说明:尽管上面的答案是按字典序排列的,但是你可以任意选择答案输出的顺序。

阅读全文

Leetcode 236:二叉搜索树中第K小的元素(最详细的解法!!!)

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。” 例如,给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4] 1234567 _______3______ / \ ___5__ ___1__/ \ / \6 _2 0 8 / \ 7 4 示例 1: 123输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1输出: 3解释: 节点 5 和节点 1 的最近公共祖先是节点 3。 示例 2: 123输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4输出: 5解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。 说明: 所有节点的值都是唯一的。 p、q 为不同节点且均存在于给定的二叉树中。

阅读全文

Leetcode 230:二叉搜索树中第K小的元素(最详细的解法!!!)

给定一个二叉搜索树,编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。 说明:你可以假设 k 总是有效的,1 ≤ k ≤ 二叉搜索树元素个数。 示例 1: 1234567输入: root = [3,1,4,null,2], k = 1 3 / \ 1 4 \ 2输出: 1 示例 2: 123456789输入: root = [5,3,6,2,4,null,null,1], k = 3 5 / \ 3 6 / \ 2 4 / 1输出: 3 进阶:如果二叉搜索树经常被修改(插入/删除操作)并且你需要频繁地查找第 k 小的值,你将如何优化 kthSmallest 函数?

阅读全文

Leetcode 108:将有序数组转换为二叉搜索树(最详细的解法!!!)

将一个按照升序排列的有序数组,转换为一棵高度平衡二叉搜索树。 本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。 示例: 123456789给定有序数组: [-10,-3,0,5,9],一个可能的答案是:[0,-3,9,-10,null,5],它可以表示下面这个高度平衡二叉搜索树: 0 / \ -3 9 / / -10 5

阅读全文

Leetcode 450:删除二叉搜索树中的节点(最详细的解法!!!)

给定一个二叉搜索树的根节点 root 和一个值 key,删除二叉搜索树中的 key 对应的节点,并保证二叉搜索树的性质不变。返回二叉搜索树(有可能被更新)的根节点的引用。 一般来说,删除节点可分为两个步骤: 首先找到需要删除的节点; 如果找到了,删除它。 说明: 要求算法时间复杂度为 O(h),h 为树的高度。 示例: 1234567891011121314151617181920212223242526root = [5,3,6,2,4,null,7]key = 3 5 / \ 3 6 / \ \2 4 7给定需要删除的节点值是 3,所以我们首先找到 3 这个节点,然后删除它。一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。 5 / \ 4 6 / \2 7另一个正确答案是 [5,2,6,null,4,null,7]。 5 / \ 2 6 \ \ 4 7

阅读全文

Leetcode 98:验证二叉搜索树(最详细的解法!!!)

给定一个二叉树,判断其是否是一个有效的二叉搜索树。 假设一个二叉搜索树具有如下特征: 节点的左子树只包含小于当前节点的数。 节点的右子树只包含大于当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树。 示例 1: 12345输入: 2 / \ 1 3输出: true 示例 2: 123456789输入: 5 / \ 1 4 / \ 3 6输出: false解释: 输入为: [5,1,4,null,null,3,6]。 根节点的值为 5 ,但是其右子节点值为 4 。

阅读全文