【树】Kth Smallest Element in a BST（递归）

题目：

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.

思路：

1、计算左子树元素个数leftSize。

2、 leftSize+1 = K，则根节点即为第K个元素

     leftSize >=k, 则第K个元素在左子树中，

     leftSize +1 <k, 则转换为在右子树中，寻找第K-left-1元素。

/*** Definition for a binary tree node.* function TreeNode(val) {* this.val = val;* this.left = this.right = null;* }*/ /*** @param {TreeNode} root* @param {number} k* @return {number}*/ var kthSmallest = function(root, k) {if(root==null){return 0;}var leftSize=nodeNum(root.left);if(k==leftSize+1){return root.val;}else if(k<leftSize+1){return kthSmallest(root.left,k);}else{return kthSmallest(root.right,k-leftSize-1);} };function nodeNum(root){if(root==null){return 0;}else{return 1+nodeNum(root.left)+nodeNum(root.right);} }

 

转载于:https://www.cnblogs.com/shytong/p/5169013.html

总结

以上是生活随笔为你收集整理的【树】Kth Smallest Element in a BST（递归）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。