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?
思路：就是利用中序遍歷的結(jié)果是遞增的，然后找到第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; }};新聞熱點(diǎn)
疑難解答
