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

三种做法
总体来说 采用非递归的效率比其他方式实现要好一点 占用内存稍微小一点
1、非递归，采用中序遍历，求出第k个节点

    vector<TreeNode *> tp;
    void inOrder(TreeNode *root) { //使用中序遍历得到有序数组
        if(!root)
            return;
        inOrder(root->left);
        tp.push_back(root);
        inOrder(root->right);
    }
    TreeNode* KthNode(TreeNode* pRoot, int k) {
        if(!pRoot)
            return NULL;
        inOrder(pRoot);
        for(int i = 0; i < tp.size(); i++) {
            if(i == k-1)
                return tp[i];
        }
        return NULL;
    }

2、递归做法，无返回值的

    TreeNode *tp = NULL; //保存最终的结果
    void midOrder(TreeNode *pRoot, int &k) { //也是要用引用
        if(!pRoot || tp) //tp不为空 直接返回  也是避免无谓
            return;

        midOrder(pRoot->left, k);
        k--;
        if(k == 0) {
            tp = pRoot;
            return;
        }
        midOrder(pRoot->right, k);
    }
    TreeNode* KthNode(TreeNode* pRoot, int k) {
       if(!pRoot)
           return NULL;
        midOrder(pRoot, k);
        return tp;
    }

3、递归做法，有返回值的

//也是递归使用中序遍历，当k为0时 找到节点  如果开始没有找到结果 递归返回的都是NULL
//一旦找到结果 就会把这个结果层层返回
TreeNode * getRes(TreeNode *pRoot, int &k) { //主要要用引用 保证递归的过程只能使用
//一个变量 因为每层递归的k值是不同的
        if(!pRoot)
            return NULL;
        TreeNode *left = getRes(pRoot->left, k);
        if(left){ //不为空 找到结果  及时返回  可以避免后面的递归
            return left;
        }
        k--;
        if(k == 0) {
            return pRoot;
        }
        TreeNode *right = getRes(pRoot->right, k);
        if(right){ //不为空 找到结果  及时返回  可以避免后面的递归
            return right;
        }
        return left ? left : right ? right : NULL; //这里主要是返回NULL
    }
    TreeNode* KthNode(TreeNode* pRoot, int k) {
       if(!pRoot)
           return NULL;
        int tk = k;
        return getRes(pRoot, k);
    }