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

题目描述

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

题解：

　　考察的就是中序遍历

　　不过注意进行剪枝

 1 class Solution {
 2 public:
 3     TreeNode* KthNode(TreeNode* pRoot, int k)
 4     {
 5         if (pRoot == nullptr)return nullptr;
 6         inOrder(pRoot, k);
 7         return res;
 8     }
 9     void inOrder(TreeNode* pRoot, const int k)
10     {
11         if (n > k || pRoot == nullptr)return;//进行剪枝和边界处理
12         inOrder(pRoot->left, k);
13         ++n;
14         if (n == k && res == nullptr)
15         {
16             res = pRoot;
17             return;
18         }
19         inOrder(pRoot->right, k);
20     }
21 private:
22     int n = 0;
23     TreeNode *res = nullptr;
24 };