두 갈래 나무 응용_두 갈래 검색 트리의 K 노드
2764 단어 두 갈래 나무의 흔한 문제문제를 풀고 기록하다
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
*/
class Solution {
int number=0;
public:
// ,
TreeNode* KthNode(TreeNode* pRoot, int k)
{
if(pRoot)
{
TreeNode* node=KthNode(pRoot->left,k);
if(node!=NULL)
return node;
++number;
if(number==k)
return pRoot;
node=KthNode(pRoot->right,k);
if(node!=NULL)
return node;
}
return NULL;
}
/*
// , K vec[K-1] ;
TreeNode* KthNode(TreeNode* pRoot, unsigned int k)
{
if(pRoot==NULL||k<=0) return NULL;
vector*> vec;
Inorder(pRoot,vec);
if(k>vec.size())
return NULL;
return vec[k-1];
}
// , vector
void Inorder(TreeNode* pRoot,vector*>& vec)
{
if(pRoot==NULL) return;
Inorder(pRoot->left,vec);
vec.push_back(pRoot);
Inorder(pRoot->right,vec);
}
*/
};