剑指offer——面试题63：二叉搜索树的第k个结点

Solution1:

20180916重做

/*
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<struct TreeNode*> result;
        Pre_travel(pRoot, result);
        if(result.size() < k)
            return NULL;
        return result[k - 1];
    }
    void Pre_travel(struct TreeNode* pRoot, 
                    vector<struct TreeNode*> &res) {
        if (!pRoot)
            return;
        if(pRoot->left)
            Pre_travel(pRoot->left, res);
        res.push_back(pRoot);
        if(pRoot->right)
            Pre_travel(pRoot->right, res);
    }
};

Solution2:

利用二叉搜索树已经有序的性质，直接用中序遍历，得到第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;
        return Inorder_travel(pRoot, k);
    }

    struct TreeNode* Inorder_travel(struct TreeNode *pRoot, int &k) {
        struct TreeNode *res = NULL;
        if(pRoot->left != NULL)
            res = Inorder_travel(pRoot->left, k);
        if(res == NULL) {
            if(k == 1)
                res = pRoot;
            k--;
        }
        if(res == NULL && pRoot->right != NULL)
            res = Inorder_travel(pRoot->right, k);
        return res;
    }
};