二叉搜索树的第k个结点

时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M

题目描述

给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8） 中，按结点数值大小顺序第三小结点的值为4。

思路：

根据二叉搜索树的特性：左小右大，采用中序遍历二叉树，得到的序列即为有序序列，然后再找第k个结点

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    TreeNode* KthNode(TreeNode* pRoot, int k)
    {
        if(pRoot == NULL || k <= 0)
            return NULL;
        vector<TreeNode*> vec;
        InOrder(pRoot,vec);
        if(k > vec.size())
            return NULL;
        return vec[k-1];
    }
    void InOrder(TreeNode* pRoot,vector<TreeNode*>& vec)
    {
        if(pRoot == NULL )
            return ;
        InOrder(pRoot->left,vec);
        vec.push_back(pRoot);
        InOrder(pRoot->right,vec);
    }

};

上述方法需要遍历整棵树，取得第k个元素，复杂度为O(n)，可在中序遍历的同时，设置一个计数器，用于记数，当等于k时，停止递归遍历。

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    int count = 0;
    TreeNode* KthNode(TreeNode* pRoot, int k)
    {
        if(pRoot!=NULL)
        {
            TreeNode* node = KthNode(pRoot->left,k);
            if(node != NULL)
                return node;
            count++;
            if(count == k)
                return pRoot;
            node = KthNode(pRoot->right,k);
            if(node != NULL)
                return node;
        }
        return NULL;
    }
};