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

题意思路：
给定一棵二叉搜索树，请找出其中的第k小的TreeNode结点。
二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树：

若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；

若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；

它的左、右子树也分别为二叉排序树。

方法一:中序递归遍历二叉树
中序递归就是二叉搜索树的第个结点；

若二叉树为空则结束返回，否则：

（1）中序遍历左子树

（2）访问根结点

（3）中序遍历右子树

通过搜索顺序寻找第个结点

复杂度分析

时间复杂度：O()，表示二叉树结点数量，递归中序遍历所有结点。

空间复杂度：O()，递归开辟新空间。

图文详解：

/*
struct TreeNode {//定义二叉树
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    TreeNode* res;
    void inorder(TreeNode* root,int &k){
        if(root==nullptr)return ;//如果当前结点为空返回
        inorder(root->left,  k);//递归遍历左子树
        k--;//枚举第i个结点
        if(k==0) res=root;
        inorder(root->right,  k);//递归遍历右子树
    }
    TreeNode* KthNode(TreeNode* pRoot, int k) {
       inorder(pRoot,k);//递归中序遍历
        return res;
    }


};

方法二:非递归中序遍历二叉树

通过栈来非递归模拟二叉树的中序遍历

沿着左子树一直加入栈中

取栈顶结点访问

对当前栈顶结点的右子树进行同样方式的访问

复杂度分析

时间复杂度：O()，表示二叉树结点数量，非递归中序遍历所有结点。

空间复杂度：O()，所有结点可能会全部入栈。

/*
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)return nullptr;//特判根结点为空时
        stack<TreeNode*>res;//用栈模拟非递归
        TreeNode* head=pRoot;
        while(res.size()||head){//如果当前栈内不为空或者结点当前有值
            while(head){//当前结点不为空时
                res.push(head);//将其左子树加入栈中
                head=head->left;
            }
            TreeNode* node =res.top();//弹出栈顶结点
            res.pop();
            if(--k==0)return node;//枚举第k小结点
              head=node->right;//当前结点等于右子树
        }
        return nullptr;
    }


};