衡阳公司做网站腾讯广告平台

Problem: 230. 二叉搜索树中第K小的元素

题目描述

思路

直接利用二叉搜索树中序遍历为一个有序序列的特性：

记录一个int变量rank，在中序遍历时若当前rank == k则返回当前节点值

复杂度

时间复杂度:

$O(n)$;其中$n$为二叉树中节点的个数

空间复杂度:

$O(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);}
}