题解 | 二叉搜索树的第k个节点

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
#include <pthread.h>
class Solution {


    int count = 0; // this is the global count of current visited value
    TreeNode* ret = nullptr;

    void midOrder(TreeNode* proot, int k) {
        if (proot == nullptr || count > k) {
            return;
        }

        midOrder(proot->left, k);

        count++;

        if (count == k) {
            ret = proot;
        }

        midOrder(proot->right, k);

    }

public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param proot TreeNode类 
     * @param k int整型 
     * @return int整型
     */
    int KthNode(TreeNode* proot, int k) {
        // write code here
        // if (proot == nullptr)
        //     return -1;
        midOrder(proot, k);

        if (ret == nullptr)
            return -1;
        else 
            return ret->val;



    }
};

这段递归代码的逻辑很重要。

首先我们思考，这个是需要从最左下角开始标定的，但是因为数据结构中并不存在prev这样的指针，所以本身这个就不现实。

这个问题能用递归去解决，原因在于，他是一层套一层的，做到最左下角然后开始recursively bottom up，很符合recursion的原理。

我们开始设计，我们需要一个global的count去记录我遍历的点的个数，然后我根据要求，先遍历左边的点， 然后遍历右边的点，然后再看root node。

因此我们这个recursive function里，需要先对左边的做递归，#剑指offer#

** 这里的count++是对root的操作，左边归左边，右边归右边