Jz54 二叉搜索树的第K个结点

描述

给定一棵结点数为n 二叉搜索树，请找出其中的第 k 小的TreeNode结点值。

1.返回第k小的节点值即可

2.不能查找的情况，如二叉树为空，则返回-1，或者k大于n等等，也返回-1

3.保证n个节点的值不一样

二叉搜索树的第k个节点_牛客题霸_牛客网

二叉搜索树值的特点：left < mid < right

思路：copy by 二叉搜索树的第k个节点_牛客题霸_牛客网

        根据二叉搜索树的性质，我们可以尝试递归中序遍历，也就是从最小的一个节点开始，找到k个就是我们要找的目标。

1.栈实现

	//Solution1: Stack Inorder  O(N) O(N)
int KthNode(TreeNode* proot, int k) {// write code hereif(!proot)return -1;TreeNode *pCur = proot;stack<TreeNode*>  treeStack;// treeStack.push(pCur);int cnt =  0;while(!treeStack.empty() || pCur ){while(pCur){treeStack.push(pCur);pCur = pCur->left;}TreeNode *popNode = treeStack.top();treeStack.pop();if(--k == 0)return popNode->val;pCur = popNode->right;}return -1;}

2.递归

	//Solution 2:inorder recursive O(N) O(N)int count = 0;TreeNode *res = nullptr;void findKthNode(TreeNode *proot, int k){ if(!proot || count > k) return;findKthNode(proot->left, k);if(++count == k) res = proot;findKthNode(proot->right, k);}int KthNode(TreeNode *proot, int k){findKthNode(proot, k);if(res) return res->val;else return -1;}