題目:
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大數。這裡是BST,已經有順序,更方便一些。
如果左子樹數目大於等於K,那麼直接找左子樹中第K個;如果左子樹數目等於 K-1,那麼根節點就是第K個;如果左子樹數目小於K,那麼直接找右子樹中第(K - leftSum - 1)個(勿忘根節點) 關於左子樹有多少結點?需要另一個遞歸程序計算。
/** * 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 findNodeSum(TreeNode* root) { if (root == NULL) return 0; return (findNodeSum(root->left) + findNodeSum(root->right) + 1); } int kthSmallest(TreeNode* root, int k) { int leftSum = findNodeSum(root->left); if (leftSum >= k) return kthSmallest(root->left, k); else if (leftSum == k - 1) return root->val; else { return kthSmallest(root->right,k - leftSum - 1); } } };題目到這兒還沒完,如果BST總是在修改呢?
最好應該修改樹結點的結構,增加一項屬性:左子樹的節點總數。這樣搜索的復雜度就是 O (height)