题目描述
给定一棵二叉搜索树,请找出其中的第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 };