[LeetCode]230.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个就终止遍历。

代码

/*---------------------------------------
*   日期：2015-08-03
*   作者：SJF0115
*   题目: 230.Kth Smallest Element in a BST
*   网址：https://leetcode.com/problems/kth-smallest-element-in-a-bst/
*   结果：AC
*   来源：LeetCode
*   博客：
-----------------------------------------*/
#include <iostream>
#include <vector>
#include <stack>
using namespace std;

struct TreeNode{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x),left(nullptr),right(nullptr){}
};

class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        if(k <= 0 || root == nullptr){
            return -1;
        }//if
        int result = 0;
        int index = 0;
        InOrder(root,k,index,result);
        return result;
    }
private:
    void InOrder(TreeNode* root,int k,int &index,int &result){
        if(root){
            if(root->left){
                InOrder(root->left,k,index,result);
            }//if
            ++index;
            // 找到目标则不用遍历
            if(index > k){
                return;
            }//if
            // 找到目标
            if(index == k){
                result = root->val;
                return;
            }//if
            if(root->right){
                InOrder(root->right,k,index,result);
            }//if
        }//if
    }
};

int main(){
    Solution s;
    int k = 7;
    TreeNode *root = new TreeNode(5);
    TreeNode *node1 = new TreeNode(2);
    TreeNode *node2 = new TreeNode(3);
    TreeNode *node3 = new TreeNode(4);
    TreeNode *node4 = new TreeNode(9);
    TreeNode *node5 = new TreeNode(6);
    TreeNode *node6 = new TreeNode(7);
    TreeNode *node7 = new TreeNode(11);

    root->left = node2;
    root->right = node4;
    node2->left = node1;
    node2->right = node3;
    node4->left = node5;
    node4->right = node7;
    node5->right = node6;

    cout<<s.kthSmallest(root,k)<<endl;
    return 0;
}

运行时间

<script type="text/javascript"> $(function () { $('pre.prettyprint code').each(function () { var lines = $(this).text().split('\n').length; var $numbering = $('<ul/>').addClass('pre-numbering').hide(); $(this).addClass('has-numbering').parent().append($numbering); for (i = 1; i <= lines; i++) { $numbering.append($('<li/>').text(i)); }; $numbering.fadeIn(1700); }); }); </script>