题目描述:给定一个二叉搜索树的根节点
root
,和一个整数k
,请你设计一个算法查找其中第k
个最小元素(从 1 开始计数)。示例说明请见LeetCode官网。
来源:力扣(LeetCode)
https://leetcode-cn.com/problems/kth-smallest-element-in-a-bst/
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解法一:二叉树的中序遍历、
二叉搜索树的特性即中序遍历结果就是节点的顺序排列,所以通过中序遍历的方式来查找第k个最小元素,处理过程如下:
- 首先判断特殊情况,如果二叉树为空,说明没有第K小的节点,直接返回空;
- 中序遍历得到二叉搜索树的所有节点,是按顺序排列的;
- 判断如果k大于二叉树的节点数,说明不存在第K小的节点,直接返回空;
- 返回第K小的节点。
import com.kaesar.leetcode.TreeNode; import java.util.ArrayList; import java.util.List; public class LeetCode_230 { public static int kthSmallest(TreeNode root, int k) { // 如果二叉树为空,说明没有第K小的节点,直接返回空 if (root == null) { return -1; } List<Integer> values = new ArrayList<>(); // 中序遍历得到二叉搜索树的所有节点,是按顺序的 inOrder(root, values); // 如果k大于二叉树的节点数,说明不存在第K小的节点,直接返回空 if (k > values.size()) { return -1; } // 返回第K小的节点 return values.get(k - 1); } /** * 二叉树的中序遍历 * * @param root * @param values */ private static void inOrder(TreeNode root, List<Integer> values) { if (root.left != null) { inOrder(root.left, values); } values.add(root.val); if (root.right != null) { inOrder(root.right, values); } } public static void main(String[] args) { /** * 测试用例: * 3 * 1 4 * 2 */ TreeNode root = new TreeNode(3); root.left = new TreeNode(1); root.right = new TreeNode(4); root.left.right = new TreeNode(2); // 期望输出: 1 System.out.println(kthSmallest(root, 1)); } }
【每日寄语】 我们的希望是今天比昨天好,明天对于我们来说太遥远了,无所谓。人活着一生不能做萤火虫,永远要当一个钻井工人,永远在头上,为了前面的光芒努力,不是看后面怎么样。希望我们的过去再美好也是由于我们过去的努力,今天再努力就是为了明天的辉煌。