[leetcode]230. Kth Smallest Element in a BST

---

Analysis

ummmm—— [每天刷题并不难。。。其实已经很多天没刷了]

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.

Implement

方法一（中序遍历BST，然后输出第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 kthSmallest(TreeNode* root, int k) { helper(root, k); return val[k-1]; } void helper(TreeNode* node, int k){ if(!node) return ; helper(node->left, k); val.push_back(node->val); helper(node->right, k); } private: vector<int> val; };

方法二（Follow up里面提到BST可能频繁的插入删除等，所以可以用分治法，先确定第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 kthSmallest(TreeNode* root, int k) { int cnt = count(root->left); if(k <= cnt) return kthSmallest(root->left, k); else if(k > cnt+1) return kthSmallest(root->right, k-cnt-1); return root->val; } int count(TreeNode* node){ if(!node) return 0; return 1+count(node->left)+count(node->right); } };