剑指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 };

 

 
上一篇:PAT甲级——A1102 Invert a Binary Tree


下一篇:VB 替换word文档中页眉页脚的文字