'검 지 오 프' 이 진 트 리 의 k 번 째 결점 검색

【 성명: 판권 소유, 전재 출처 표시, 상업 용도 로 사용 하지 마 십시오. 연락처:[email protected]] 제목 링크:http://www.nowcoder.com/practice/ef068f602dde4d28aab2b210e859150a?rp=4&ru=/ta/coding- interviews & qru = / ta / coding - interviews / question - ranking 제목 설명 은 두 번 째 검색 트 리 를 지정 하 였 습 니 다. 그 중 k 번 째 큰 결점 을 찾 아 보 세 요.예 를 들 어 5 / \ 3 7 / \ / \ \ 2468 에서 결점 수치 크기 순 으로 세 번 째 결점 의 값 은 4 이다.사고방식 은 두 갈래 검색 트 리 에 있어 서 정렬 된 수열 을 얻 으 려 면 중간 순서 로 옮 겨 다 니 는 것 이 필요 하 다. 그래서 우 리 는 마지막 에 옮 겨 다 니 는 과정 에서 k 번 째 로 옮 겨 다 니 는 결점

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution
{
	public:
		TreeNode* KthNode(TreeNode* pRoot, unsigned int k)
		{
			if(pRoot==nullptr || k==0)
				return nullptr;
			return KthNodeCore(pRoot,k);
		}
		TreeNode *KthNodeCore(TreeNode *root, unsigned int& k)
		{
			TreeNode *target = nullptr;

			if(root->left!=nullptr)
				target = KthNodeCore(root->left,k);

			if(target==nullptr)
			{
				if(k==1)
					target=root;
				k--;
			}

			if(target==nullptr && root->right!=nullptr)
				target = KthNodeCore(root->right,k);

			return target;
		}
};

을 찾 아야 한다.