#include <bits/stdc++.h>
using namespace std;

struct TreeNode
{
	int val;
	TreeNode *left, *right;
	TreeNode(int x = 0) : val(x), left(nullptr), right(nullptr) {}
};

// 基本操作
int countNodes(TreeNode *root)
{
	return root ? 1 + countNodes(root->left) + countNodes(root->right) : 0;
}

int maxDepth(TreeNode *root)
{
	return root ? 1 + max(maxDepth(root->left), maxDepth(root->right)) : 0;
}

int countLeaves(TreeNode *root)
{
	if (!root)
		return 0;
	if (!root->left && !root->right)
		return 1;
	return countLeaves(root->left) + countLeaves(root->right);
}

TreeNode *invertTree(TreeNode *root)
{
	if (!root)
		return nullptr;
	swap(root->left, root->right);
	invertTree(root->left);
	invertTree(root->right);
	return root;
}

// 遍历
void preorder(TreeNode *root)
{
	if (!root)
		return;
	cout << root->val << " ";
	preorder(root->left);
	preorder(root->right);
}

void inorder(TreeNode *root)
{
	if (!root)
		return;
	inorder(root->left);
	cout << root->val << " ";
	inorder(root->right);
}

void postorder(TreeNode *root)
{
	if (!root)
		return;
	postorder(root->left);
	postorder(root->right);
	cout << root->val << " ";
}

void levelorder(TreeNode *root)
{
	if (!root)
		return;
	queue<TreeNode *> q;
	q.push(root);
	while (!q.empty())
	{
		TreeNode *u = q.front();
		q.pop();
		cout << u->val << " ";
		if (u->left)
			q.push(u->left);
		if (u->right)
			q.push(u->right);
	}
}

// 二叉搜索树
TreeNode *searchBST(TreeNode *root, int target)
{
	while (root && root->val != target)
		root = (target < root->val) ? root->left : root->right;
	return root;
}

TreeNode *insertBST(TreeNode *root, int val)
{
	if (!root)
		return new TreeNode(val);
	if (val < root->val)
		root->left = insertBST(root->left, val);
	else
		root->right = insertBST(root->right, val);
	return root;
}

TreeNode *findMin(TreeNode *root)
{
	while (root->left)
		root = root->left;
	return root;
}

TreeNode *deleteBST(TreeNode *root, int key)
{
	if (!root)
		return nullptr;
	if (key < root->val)
		root->left = deleteBST(root->left, key);
	else if (key > root->val)
		root->right = deleteBST(root->right, key);
	else
	{
		if (!root->left)
		{
			TreeNode *r = root->right;
			delete root;
			return r;
		}
		if (!root->right)
		{
			TreeNode *l = root->left;
			delete root;
			return l;
		}
		TreeNode *minNode = findMin(root->right);
		root->val = minNode->val;
		root->right = deleteBST(root->right, minNode->val);
	}
	return root;
}

// 重建二叉树
unordered_map<int, int> pos;

TreeNode *buildFromPreIn(vector<int> &pre, vector<int> &in, int l1, int r1, int l2, int r2)



{
	if (l1 > r1)
		return nullptr;
	int rootVal = pre[l1];
	TreeNode *root = new TreeNode(rootVal);
	int k = pos[rootVal];
	int leftLen = k - l2;
	root->left = buildFromPreIn(pre, in, l1 + 1, l1 + leftLen, l2, k - 1);
	root->right = buildFromPreIn(pre, in, l1 + leftLen + 1, r1, k + 1, r2);
	return root;
}
TreeNode *buildTree(vector<int> &pre, vector<int> &in)
{
	pos.clear();
	// 修复警告：强制转换 size_t 为 int
	for (int i = 0; i < (int)in.size(); ++i)
		pos[in[i]] = i;
	return buildFromPreIn(pre, in, 0, pre.size() - 1, 0, in.size() - 1);
}

// 树的直径
int diameter = 0;
int dfsDiameter(TreeNode *root)
{
	if (!root)
		return 0;
	int leftH = dfsDiameter(root->left);
	int rightH = dfsDiameter(root->right);
	diameter = max(diameter, leftH + rightH);
	return max(leftH, rightH) + 1;
}
int getDiameter(TreeNode *root)
{
	diameter = 0;
	dfsDiameter(root);
	return diameter;
}

// LCA (递归)
TreeNode *lca(TreeNode *root, TreeNode *p, TreeNode *q)
{
	if (!root || root == p || root == q)
		return root;
	TreeNode *left = lca(root->left, p, q);
	TreeNode *right = lca(root->right, p, q);
	if (left && right)
		return root;
	return left ? left : right;
}

// 平衡二叉树判断
bool isBalanced(TreeNode *root, int &height)
{
	if (!root)

	{
		height = 0;
		return true;
	}
	int lh, rh;
	if (!isBalanced(root->left, lh))
		return false;
	if (!isBalanced(root->right, rh))
		return false;
	if (abs(lh - rh) > 1)
		return false;
	height = max(lh, rh) + 1;
	return true;
}
bool isBalancedTree(TreeNode *root)
{
	int h;
	return isBalanced(root, h);
}

// 完全二叉树判断
bool isCompleteTree(TreeNode *root)
{
	if (!root)
		return true;
	queue<TreeNode *> q;
	q.push(root);
	bool nullSeen = false;
	while (!q.empty())

	{
		TreeNode *u = q.front();
		q.pop();
		if (!u)
		{
			nullSeen = true;
		}
		else
		{
			if (nullSeen)
				return false;
			q.push(u->left);
			q.push(u->right);
		}
	}
	return true;
}

// 满二叉树判断（兼容 C++11）
pair<int, bool> checkFull(TreeNode *root)
{
	if (!root)
		return make_pair(0, true);
	pair<int, bool> left = checkFull(root->left);
	pair<int, bool> right = checkFull(root->right);
	int lh = left.first, lf = left.second;
	int rh = right.first, rf = right.second;
	bool isFull = lf && rf && (lh == rh);
	return make_pair(max(lh, rh) + 1, isFull);
}

bool isFullTree(TreeNode *root)
{
	return checkFull(root).second;
}

// 清理内存
void deleteTree(TreeNode *root)
{
	if (!root)
		return;
	deleteTree(root->left);
	deleteTree(root->right);
	delete root;
}

// ================= 示例 main 函数（请按需取消注释并修改） =================
int main()
{
	// 示例：创建一棵树
	TreeNode *root = new TreeNode(1);
	root->left = new TreeNode(2);
	root->right = new TreeNode(3);
	root->left->left = new TreeNode(4);
	root->left->right = new TreeNode(5);

	cout << "结点数: " << countNodes(root) << endl;
	cout << "深度: " << maxDepth(root) << endl;
	cout << "叶子数: " << countLeaves(root) << endl;

	deleteTree(root);
	return 0;
}