- 浏览: 174275 次
- 性别:
- 来自: 济南
文章分类
最新评论
Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.
Note:
You may assume k is always valid, 1 ≤ k ≤ BST's total elements.
给定一个二叉搜索树,从中找到第k小的元素。根据二叉搜索树的性质中序遍历正好是二叉搜索树的升序排列,当我们遍历到第k个元素是返回就可以了。代码如下:
我们还可以先计算出左子树的节点个数leftnum,左子树的元素都小于根节点的元素,我们用leftnum与k比较,如果k > leftnum, 则k不再左子树中,我们只需要在右子树中找到第k - leftnum个元素就可以了;如果k < leftnum, 我们继续在左子树中找第k个元素;如果相等,我们就返回左子树的根节点。代码如下:
Note:
You may assume k is always valid, 1 ≤ k ≤ BST's total elements.
给定一个二叉搜索树,从中找到第k小的元素。根据二叉搜索树的性质中序遍历正好是二叉搜索树的升序排列,当我们遍历到第k个元素是返回就可以了。代码如下:
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { int count = 0; int result = 0; public int kthSmallest(TreeNode root, int k) { if(root == null) return 0; dfs(root, k); return result; } public void dfs(TreeNode root, int k) { if(root == null) return; dfs(root.left, k); if(++count == k) { result = root.val; return; } dfs(root.right, k); } }
我们还可以先计算出左子树的节点个数leftnum,左子树的元素都小于根节点的元素,我们用leftnum与k比较,如果k > leftnum, 则k不再左子树中,我们只需要在右子树中找到第k - leftnum个元素就可以了;如果k < leftnum, 我们继续在左子树中找第k个元素;如果相等,我们就返回左子树的根节点。代码如下:
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public int kthSmallest(TreeNode root, int k) { if(root == null) return 0; int left = getNode(root.left); if(left + 1 == k) { return root.val; } else if(left + 1 < k) { return kthSmallest(root.right, k - left - 1); } else { return kthSmallest(root.left, k); } } public int getNode(TreeNode root) { if(root == null) return 0; return 1 + getNode(root.left) + getNode(root.right); } }
发表评论
-
498. Diagonal Traverse
2019-11-15 13:52 229Given a matrix of M x N eleme ... -
496 Next Greater Element I
2019-11-14 13:50 231You are given two arrays (witho ... -
Word Break II
2016-03-09 03:15 345Given a string s and a dictiona ... -
Insert Interval
2016-03-08 02:11 337Given a set of non-overlapping ... -
Merge Intervals
2016-03-07 05:25 458Given a collection of intervals ... -
Merge k Sorted Lists
2016-03-07 04:03 522Merge k sorted linked lists and ... -
Multiply Strings
2016-03-06 07:27 434Given two numbers represented a ... -
N-Queens II
2016-03-06 03:06 623Follow up for N-Queens problem. ... -
N-Queens
2016-03-06 02:47 432The n-queens puzzle is the prob ... -
First Missing Positive
2016-03-05 03:09 392Given an unsorted integer array ... -
Spiral Matrix
2016-03-04 03:39 522Given a matrix of m x n element ... -
Trapping Rain Water
2016-03-04 02:54 537Given n non-negative integers r ... -
Repeated DNA Sequences
2016-03-03 03:10 374All DNA is composed of a series ... -
Increasing Triplet Subsequence
2016-03-02 02:48 866Given an unsorted array return ... -
Maximum Product of Word Lengths
2016-03-02 01:56 884Given a string array words, fin ... -
LRU Cache
2016-02-29 10:37 559Design and implement a data str ... -
Super Ugly Number
2016-02-29 07:07 604Write a program to find the nth ... -
Longest Increasing Path in a Matrix
2016-02-29 05:56 766Given an integer matrix, find t ... -
Coin Change
2016-02-29 04:39 739You are given coins of differen ... -
Minimum Height Trees
2016-02-29 04:11 635For a undirected graph with tre ...
相关推荐
378.Kth_Smallest_Element_in_a_Sorted_Matrix有序矩阵中第K小的元素【LeetCode单
703.Kth_Largest_Element_in_a_Stream数据流中的第K大元素【LeetCode单题讲解系列】
Smallest Element in a BST Review:高效的一些建议 Tip:Elastic Search VS Solr Share:人的一生两个最大的财富是:你的才华和你的时间 Algorithm:LC 763. Partition Labels Review:Signs that You are a Bad ...
本人在Clion中的实现的第小k元素,有期望值是O(n)代价的以及醉话情况为O(n)BFPRT算法
Kth Smallest Element in a BST 二叉树的递归 Minimum Depth of Binary Tree Maximum Depth of Binary Tree Path Sum Path Sum II Binary Tree Maximum Path Sum Populating Next Right Pointers in Each Node Sum ...
lru cache leetcode Coding-Interview A repo for popular coding interview ...In ...In ...In ...二叉树查找/BST查找 Closest Binary Search Tree Value 二叉树查找/二叉树第K个 Kth Smallest Element In A
this function returns kth smallest element in arr[l...r],using quicksort based method. without sorting all the elements in the list
8 Kth Largest Element in an Array 35 9 Wildcard Matching 37 10 Regular Expression Matching in Java 39 11 Merge Intervals 43 12 Insert Interval 45 13 Two Sum 47 14 Two Sum II Input array is sorted 49 ...
smallest or largest element in array 4. Improvements in Java 8 - For HashMap if hashcode collision count is more than 8 in a row , then its internal structure is changed from linked list to tree 渐近...
此程序可实现在图面中批量替换各种类型的块,处理图时有用.
DSP语音处理芯片——在KTH15(A)矿用本安型(数字抗噪声)电话机中的应用.pdf
KTH-TIPS 纹理材质数据.zip
纹理图像分类数据集,KTH-TIPS数据集,包含orange-peel、bread等10类纹理图像
KTH-TIPS纹理灰度数据集,可以直接用于matlab图像分类
Give an O(lg m + lgn) time algorithm for computing the kth largest element in the union of the two lists. (For simplicity, you can assume that the elements of the two lists are distinct). Practice 2 ...
用于纹理图像分类的基准数据集,网上比较难找。...解压后包含kth-tips2-a_col_200x200.tar和kth-tips2-b_col_200x200.tar两个文件,a是每一类的样本数不一样,b是每一类的样本数一样,一般使用b作为数据集。
KTH数据资源在下载的时候经常会发生中断下载,导致下载的东西消失。此链接是百度云资源。绝对有效
CAD块替换,画图替换非常好用,命令 KTH
演示文稿.kth
KTH数据集使用来自的KTH人类活动识别数据集进行实验