深入理解二叉搜索树的第k个节点及其有序特性

BST有序性理解

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

解题思路:
BST本身就是有序的(左子树小于根结点, 右子树大于根结点)，中序遍历即是升序
要求第k小，即中序遍历时到达第k个元素(二叉搜索树，不存在两个相同的节点值)
采用循环中序遍历的方式(不使用递归), 拿到一个根结点, 先把所有的左节点压栈(通过根结点得到左节点,访问完左节点,才访问根结点—>根结点先进后出—> 选栈结构)
中序采用do{…}while()语句, 先让他执行一次,先把所有结点全入栈(以一个根结点出发的所有左节点)

即就是在搜素二叉树中, 中序找第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) { // 第k小(k越大,则值越大的)，那就从k开始, k是总结点个数 if(pRoot == nullptr || k <= 0){return nullptr; }stack<TreeNode*> st; // 放节点TreeNode* node = pRoot;do{while(node != nullptr){ // node指向第一个结点// 将左子树全部入栈, 先放根,再放左节点, 最后出栈的时候就是先出最左结点st.push(node);node = node->left;}// 把当前结点的所有的左子树全入了, 此时结点肯定指向nullptr, 接下来开始中序访问if(!st.empty()){ node = st.top();// 保存栈顶元素st.pop();// 已访问了一次k--;// 则k--if(k == 0){// 说明已经把对应的结点找到了return node; //其实是最大的那个结点, 也就是第k小, 输入的k就代表结点总数, 那么第k小就是倒数第几个最大的}// 访问完左子树node = node->right;// 压右子树, 下次循环时,又把这个结点的所有左节点全入栈了}}while (node != nullptr || !st.empty());// 说明当前的树是没有访问完的//node有可能为空(没有右节点)，但是只要stack不为空，就要继续pop求下一个。//有没有可能st为空？有可能(刚入了一个结点,发现其没有左子树,当前结点出栈之后, 栈就为空了,但是节点不为空)，这个时候就要检测node，如果node不为空，就要整体检测右子树 //走到这里，就说明没有找到 return nullptr;}
};