剑指offer——59二叉搜索树的第k大节点

题目描述

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

 

题解：

　　考察的就是中序遍历

　　不过注意进行剪枝

　　

 class Solution {

 public:

     TreeNode* KthNode(TreeNode* pRoot, int k)

     {

         if (pRoot == nullptr)return nullptr;

         inOrder(pRoot, k);

         return res;

     }

     void inOrder(TreeNode* pRoot, const int k)

     {

         if (n > k || pRoot == nullptr)return;//进行剪枝和边界处理

         inOrder(pRoot->left, k);

         ++n;

         if (n == k && res == nullptr)

         {

             res = pRoot;

             return;

         }

         inOrder(pRoot->right, k);

     }

 private:

     int n = ;

     TreeNode *res = nullptr;

 };