剑指offer编程题—二叉搜索树的第k个结点

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

解题思路
二叉搜索树也就是二叉排序树，其本身要么是空树，要么满足如下两个特性：
1）若它的左子树不为空，则左子树上所有节点的值均小于它的根节点的值；
2）若它的右子树不为空，则它的左右子树上所有节点的值均大于它的根节点的值；
3）它的左右子树也分别为二叉排序树。
根据以上特点，容易想到二叉排序树的中序遍历序列就是树中所有节点值的递增排序序列。
所以树中第k小的结点就是中序遍历序列中的第k个结点。

题解1
递归实现二叉搜索树的中序遍历，遍历结果保存再数组中，返回数组中的第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 || k<=0) return NULL;
        vector<TreeNode*> v;
        inOrderTraverse(pRoot,v);
        if(k>v.size()) return NULL;
        return v[k-1];
    }
    void inOrderTraverse(TreeNode* pRoot,vector<TreeNode*> &v)
    {
        if(!pRoot)
            return ;
        inOrderTraverse(pRoot->left,v);
        v.push_back(pRoot);
        inOrderTraverse(pRoot->right,v);
    }
};

题解2
使用辅助栈，非递归实现二叉搜索树的中序遍历，遍历结果保存再数组中，并在数组大小为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 || k<=0) return NULL;
        vector<TreeNode*> v;
        inOrderTraverse(pRoot,v,k);
        if(k>v.size()) return NULL;
        return v[k-1];
    }
    void inOrderTraverse(TreeNode* pRoot,vector<TreeNode*> &v,int k)
    {
        if(pRoot){
            stack<TreeNode*> s;
            TreeNode* tmp=pRoot;
            while(!s.empty() || tmp){
                if(tmp){
                    s.push(tmp);
                    tmp=tmp->left;
                }
                else{
                    tmp=s.top();
                    s.pop();
                    v.push_back(tmp);
                    if(v.size()>=k) break;
                    tmp=tmp->right;
                }
            }
        }

    }
};

题解3
第二种思路的递归实现，也就是找到第k小的结点时直接结束递归，相比题解1，这在时间和空间上都更有优势。

/*
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 || k<1) return NULL;
        TreeNode* result=NULL;
        int count=k;
        inOrderTraverse(pRoot,result,count);
        return result;
    }
    void inOrderTraverse(TreeNode* pRoot,TreeNode* &result,int &count)
    {
        if(pRoot){
            inOrderTraverse(pRoot->left,result,count);
            --count;
            if(count==0){
                result=pRoot;
                return ;
            }
            inOrderTraverse(pRoot->right,result,count);
        }
    }
};