程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 【LeetCode從零單刷】Kth Smallest Element in a BST

【LeetCode從零單刷】Kth Smallest Element in a BST

編輯:C++入門知識

【LeetCode從零單刷】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.

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)

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved