有一个排序二叉树,数据类型是int型,如何找出中间大的元素。

时间:2024-06-16 10:04:51
void tree2Dll(TNode* root, TNode*& tail) {
	if (!root) {
		return;
	}
	if (root->left) {
		tree2Dll(root->left, tail);
	}
	TNode* tmp = root;
	tmp->left = tail;
	if (tail) {
		tail->right = tmp;
	}
	tail = tmp;

	if (root->right) {
		tree2Dll(root->right, tail);
	}
}

int findMedian(TNode* tail) {
	if (!tail) {
		return INT_MAX;
	}

	TNode* fast = tail;
	TNode* slow = tail;
	while (fast && slow) {
		if (!(fast->left)) {
			return slow->data;
		} else if (fast->left && !(fast->left->left)) {
			return (slow->data + slow->left->data) >> 1;
		} else {
			slow = slow->left;
			fast = fast->left->left;
		}
	}
}