230. Kth Smallest Element in a BST

2019-11-08 02:05:43

字体：大中小

来源：转载

供稿：网友

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.

Follow up: What if the BST is modified (insert/delete Operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?

思路：就是利用中序遍历的结果是递增的，然后找到第k小

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public: int rank = 0, num; bool r = true; void inorder(TreeNode* root, int k){ if(r){ if(root == NULL) return ; inorder(root->left, k); ++rank; if(rank == k) { num = root->val; r = false; return; } inorder(root->right, k); } } int kthSmallest(TreeNode* root, int k) { inorder(root, k); return num; }};

上一篇：Groovy动态访问

下一篇：Bayes贝叶斯方法-均值和协方差参数估计及定理证明(二)