你今天学算法了吗?打卡第四天
目录
一、题目
1、题目描述
2、基础框架
3、原题链接
二、解题报告
1、思路分析
2、时间复杂度
3、代码详解
三、本题小知识
一、题目
1、题目描述
给定一个二叉搜索树的根节点
root
,和一个整数k
,请你设计一个算法查找其中第k
个最小元素(从 1 开始计数)。示例 1:
输入:root = [3,1,4,null,2], k = 1输出:1示例 2:
输入:root = [5,3,6,2,4,null,null,1], k = 3输出:3提示:
- 树中的节点数为
n
。1 <= k <= n <= 104
0 <= Node.val <= 104
2、基础框架
Java 版本给出的基础框架代码如下:
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */class Solution { public int kthSmallest(TreeNode root, int k) { }}
3、原题链接
LeetCode 230. 二叉搜索树中第K小的元素
二、解题报告
1、思路分析
(1)先定义个查找子结点个数的函数
(2)查找左子树节点个数为leftN,如果K==leftN+1,则所查找节点为根结点
(3)如果K<=leftN,则所查找节点在左子树上 kthSmallest(root.left,k)
(4)如果K>leftN+1,则所查找节点在右子树上 kthSmallest(root.right,k-left-1)
注意:二叉搜索树,左子树结点都比根节点小,右子树结点都比根节点大;
2、时间复杂度
缺,补!
3、代码详解
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */class Solution { public int kthSmallest(TreeNode root, int k) { //查找左子树的结点int leftN = findChildNums(root.left); //左子树的结点个数加一等k则根节点的即为第k小的if(leftN+1==k){ return root.val; //左子树的结点个数加一小于k则第k小的在右子树,且为第k-leftN-1个}else if(leftN+1<k){ return kthSmallest(root.right,k-leftN-1); //左子树的结点个数大于k则第k小的在左节点}else{ return kthSmallest(root.left,k);} } /** *查找子节点个数 * @param root * @return */ public int findChildNums(TreeNode root) { if(root == null){ return 0; } return findChildNums(root.left)+findChildNums(root.right)+1; }}
三、本题小知识
三数之和,枚举;