第3题：二叉搜索树的第k个节点

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

1. 返回第k小的节点值即可
2. 不能查找的情况，如二叉树为空，则返回-1，或者k大于n等等，也返回-1
3. 保证n个节点的值不一样

• 思路
  • 递归中序遍历
    二叉搜索树：左子树的元素都小于根节点，右子树的元素都大于根节点。因此它的中序遍历（左中右）序列正好是由小到大的次序。
    • 具体做法
      1. 设置全局变量count记录遍历了多少个节点，res记录第k个节点。
      2. 另写一函数进行递归中序遍历，当节点为空或者超过k时，结束递归，返回。
      3. 优先访问左子树，再访问根节点，访问时统计数字，等于k则找到。
      4. 最后访问右子树

  class Solution {
  public:
  	//记录返回的节点
  	TreeNode* res = NULL;
  	//记录中序遍历了多少个
  	int count = 0;
  	//当遍历到节点为空或者超过k时，返回
  	void midOrder(TreeNode* root, int k){
  		if(root == NULL || count > k) 
  			return;
  		midOrder(root->left, k);
  		count++;
  		//只记录第k个
  		if(count == k)
  			res = root;
  		midOrder(root->right, k);
  	}
  	int KthNode(TreeNode* proot, int k) {
  		midOrder(proot, k);
  		if(res)
  			return res->val;
  		//二叉树为空，或是找不到
  		else 
  			return -1;
  	}
  };
  

  • 栈
    • 具体做法
      1. 用栈记录当前节点，不断往左深入，直到左边子树为空。
      2. 再弹出栈顶（即为当前子树的父节点），访问该节点，同时计数
      3. 然后再访问其右子树，其中没棵子树都遵循左中右的次序
      4. 直到第k个节点返回，如果遍历结束也没找到，则返回-1.
    • 代码

    class Solution{
    	public:
    		int kthNode(TreeNode* proot,int k){
    			if(proot==nullptr) return -1;
    			int count = 0;
    			TreeNode* p = nullptr;
    			stack<TreeNode*> s;
    			while(!s.empty()||proot!=nullptr){
    				while(proot!=nullptr){
    					s.push(proot);
    					proot = proot->left;
    				}
    				p = s.top();
    				s.pop();
    				count++;
    				if(count==k) return p->val;
    				proot = p->right;
    			}
    			return -1;
    		}
    }