例题-二叉树的深度

题目描述

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

原理

二叉搜索树按照中序遍历的顺序打印出来正好就是排序好的顺序。所以，按照中序遍历顺序找到第k个结点就是结果。

代码实现

class TreeNode 
{
public:
	int data;
	TreeNode* lchild = nullptr;
	TreeNode* rchild = nullptr;
	TreeNode(int data) :data(data) {};
	~TreeNode() {};
};

class Tree 
{
public:
	int count = 0;
	TreeNode* KthNode(TreeNode* pRoot, int k)
	{//二叉搜索树的第k的节点
    	if (pRoot != nullptr)
    	{
    		TreeNode* node = KthNode(pRoot->lchild, k);
    		if (node != NULL)
    			return node;
    		count++;
    		if (count == k)
    			return pRoot;
    		node = KthNode(pRoot->rchild, k);
    		if (node != NULL)
    			return node;
    	}
	    return nullptr;
    }
};

输入:

[5,3,7,2,4,6,8],3

输出为

4