题解 力扣 LeetCode 105 从前序与中序遍历序列构造二叉树 C/C++

题目传送门：

105. 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode）https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/

每次在中序遍历序列片段中找到前序遍历序列队首，这是该层的根节点

该位置左侧是左子树，右侧是右子树

再分别在左右子树序列中进行同样操作，找到左右子树的根节点，循环往复得到整棵树

每次找到一层的根节点就从前序遍历序列中出队它

前序遍历序列队列队首用head标记

arrSize表示该次能访问的中序遍历序列片段的长度，若 <= 0，说明该层没有节点，返回 NULL

这就是递归的终止条件

代码：

struct TreeNode* BiTree_init(int val)//节点创建&初始化
{
	struct TreeNode* p = (struct TreeNode*)malloc(sizeof(struct TreeNode));
	if (p == NULL) return NULL;
	p->val = val;
	p->left = p->right = NULL;
	return p;
}
struct TreeNode* buildTree_sub(int* prearr, int* inarr, int arrSize, int* head)
{
	if (arrSize <= 0) return NULL;
	int i;
	for (i = 0; i < arrSize && inarr[i] != prearr[*head]; i++);
	struct TreeNode* root = BiTree_init(prearr[(*head)++]);
	root->left = buildTree_sub(prearr, &inarr[0], i, head);
	root->right = buildTree_sub(prearr, &inarr[i + 1], arrSize - i - 1, head);
	return root;
}
struct TreeNode* buildTree(int* prearr, int arrSize, int* inarr, int useless)
{//多封装了一层，该次封装主要是为了在不使用全局变量和外部变量的前提下使用队列
	if (arrSize <= 0) return NULL;
	int head = 0, i;
	for (i = 0; i < arrSize && inarr[i] != prearr[head]; i++);
	struct TreeNode* root = BiTree_init(prearr[head++]);
	root->left = buildTree_sub(prearr, &inarr[0], i, &head);
	root->right = buildTree_sub(prearr, &inarr[i + 1], arrSize - i - 1, &head);
	return root;
}

拓展：

若二叉树中有相同元素，还想通过前序&中序遍历序列重构二叉树

提供的前序中序遍历结果要是存放节点地址的指针数组，而不能再是节点存放的数据

重构函数中操作的对象也要从节点数据变为节点地址

思路还是一样的，只是操作对象从数据变成地址了，就算节点数据一样，地址还都是不同的