題目描述
給定一棵二叉搜索樹，請找出其中的第k小的結點，例如， （5，3，7，2，4，6，8） 中，按結點數值大小順序第三小結點的值為4， 思路：中序遍歷二叉搜索樹，就能得到順序數列，所以先中序遍歷二叉樹，存盤在vector中，然后回傳第K-1元素，代碼如下：/*struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { }};*/class Solution {public: void mid(TreeNode * pRoot, vector<TreeNode *> & vec) { if(pRoot==NULL) return; mid(pRoot->left,vec); vec.push_back(pRoot); mid(pRoot->right,vec); } TreeNode* KthNode(TreeNode* pRoot, int k) { if(pRoot==NULL||k==0) return NULL; vector<TreeNode *> vec; mid(pRoot,vec); int i=0; if(vec.size()<k) return NULL; return vec[k-1]; } };
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/3838.html
標籤：其他
上一篇：【最新】經典面試100問，附答案