建个网站花钱做百度推广,二次开发包,青岛网站建设推广信息网络公司,阿里云免费空间Problem: 230. 二叉搜索树中第K小的元素 文章目录 题目描述思路复杂度Code 题目描述 思路
直接利用二叉搜索树中序遍历为一个有序序列的特性#xff1a; 记录一个int变量rank#xff0c;在中序遍历时若当前rank k则返回当前节点值 复杂度
时间复杂度: O ( n ) O(n) O(n);其… Problem: 230. 二叉搜索树中第K小的元素 文章目录 题目描述思路复杂度Code 题目描述 思路
直接利用二叉搜索树中序遍历为一个有序序列的特性 记录一个int变量rank在中序遍历时若当前rank k则返回当前节点值 复杂度
时间复杂度: O ( n ) O(n) O(n);其中 n n n为二叉树中节点的个数 空间复杂度: O ( h e i g h t ) O(height) O(height)其中 h e i g h t height height为二叉树的高度 Code
/*** 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 {//Recode the resultint res 0;//Recode the rank of current valueint rank 0;/*** Kth Smallest Element in a BST** param root The root of binary tree* param k Given number* return int*/public int kthSmallest(TreeNode root, int k) {traverse(root, k);return res;}/*** Kth Smallest Element in a BST(Implementation function)** param root The root of binary tree* param k Given number*/private void traverse(TreeNode root, int k) {if (root null) {return;}traverse(root.left, k);rank;if (k rank) {res root.val;return;}traverse(root.right, k);}
}
