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

題目描述

思路

直接利用二叉搜索樹中序遍歷為一個(gè)有序序列的特性：

記錄一個(gè)int變量rank，在中序遍歷時(shí)若當(dāng)前rank == k則返回當(dāng)前節(jié)點(diǎn)值

復(fù)雜度

時(shí)間復(fù)雜度:

$O(n)$;其中$n$為二叉樹中節(jié)點(diǎn)的個(gè)數(shù)

空間復(fù)雜度:

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