二叉树练习题

练习题1：单值二叉树

1.判断二叉树是单值二叉树的思路

2.代码实现

练习题2：检查两颗树是否相同

1.判断两棵树是相同的树的思路

2.代码实现

练习题3：翻转二叉树

1.翻转二叉树的思路

2.代码实现

练习题4：对称二叉树

1.判断二叉树是对称二叉树思路

2.代码实现

3.其他思路

注意：下面的思路都是不好的，效率低，所以这里就不实现了。

3.1.思路 1：先拷贝原树创建新树，新树翻转，然后再和原树判断是否相等

3.2.思路 2：先对原树的左子树进行翻转，然后再比较左右子树是否相等，最后恢复原树结构

练习题5：另一颗树的子树

1.分析

2.判断一棵树是另一棵树的子树的思路

(1)isSameTree 函数思路

(2)isSubtree 函数思路

3.代码实现

练习题6：二叉树的前序遍历

1.代码实现

2.代码分析

3.错误写法

练习题7：二叉树的中序遍历

1.代码实现

练习题8：二叉树的后序遍历

1.代码实现

练习题9：二叉树的构建及遍历

利用前序遍历创建二叉树rebuildTree

1.思路

2.代码实现

3.利用前序序列创建二叉树的代码分析

4.错误写法

4.1.错误代码

4.2.错误分析

练习题10：根据前序和中序序列创建二叉树

1.根据后序和中序序列创建二叉树的思路

2.代码实现

3.根据前序和中序序列创建二叉树的过程及图形解析

4.总结

练习题11：根据后序和中序序列创建二叉树

1.根据后序和中序序列创建二叉树的思路

2.代码实现

练习题1：单值二叉树

965. 单值二叉树 - 力扣（LeetCode）

1.判断二叉树是单值二叉树的思路

单值二叉树是指树中所有节点的值都相同的二叉树。判断一棵二叉树是否为单值二叉树可以采用递归的方法，主要思路如下：

(1)处理空树情况：空树被认为是单值二叉树，所以当根节点为空时，直接返回 true。

(2)检查当前节点与其子节点的值：

对于当前节点，分别检查其左子节点和右子节点。
如果左子节点存在，并且左子节点的值与当前节点的值不相等，说明该树不是单值二叉树，返回 false。
同理，如果右子节点存在，并且右子节点的值与当前节点的值不相等，也返回 false。

(2)递归检查子树：

如果当前节点及其左右子节点的值都相等，说明当前节点及其直接子节点满足单值条件。
接下来需要递归地检查左子树和右子树是否也满足单值条件。
只有当左子树和右子树都满足单值条件时，整棵树才是单值二叉树，所以使用逻辑与运算符 && 将递归调用的结果组合起来返回。

通过这种递归的方式，不断地检查每个节点及其子树，最终可以判断出整棵二叉树是否为单值二叉树。

2.代码实现

// 判断二叉树是否为单值二叉树的函数
// 参数 root 是二叉树的根节点指针
bool isUnivalTree(struct TreeNode* root) {// 如果根节点为空，根据定义空树可以认为是单值二叉树，返回 trueif (root == NULL)return true;// 检查当前节点的左子节点// 如果左子节点存在，并且左子节点的值与当前节点的值不相等// 说明该树不是单值二叉树，返回 falseif (root->left && root->left->val != root->val)return false;// 检查当前节点的右子节点// 如果右子节点存在，并且右子节点的值与当前节点的值不相等// 说明该树不是单值二叉树，返回 falseif (root->right && root->right->val != root->val)return false;// 若当前节点及其左右子节点的值都符合单值条件// 则递归地检查左子树和右子树是否也满足单值条件// 只有当左子树和右子树都满足单值条件时，整棵树才是单值二叉树return isUnivalTree(root->left) && isUnivalTree(root->right);
}

练习题2：检查两颗树是否相同

100. 相同的树 - 力扣（LeetCode）

1.判断两棵树是相同的树的思路

判断两棵二叉树是否相同，需要从树的结构和节点的值两个方面进行考虑。具体步骤如下：

(1)处理空节点情况：

首先检查两棵树当前节点是否都为空。如果都为空，说明这两个位置的结构是相同的，直接返回 true。
然后检查是否其中一棵树的当前节点为空，而另一棵树的当前节点不为空。如果是这种情况，说明两棵树的结构不同，返回 false。

(2)比较节点值：

如果两棵树的当前节点都不为空，比较它们的值。如果值不相等，说明这两棵树不相同，返回 false。

(3)递归比较子树：

如果当前节点的值相等，需要继续递归地比较它们的左子树和右子树。
只有当左子树和右子树都相同时，才能认为这两棵树相同。因此，使用逻辑与运算符 && 将递归调用的结果组合起来返回。

通过这种递归的方式，不断地比较两棵树的对应节点和子树，最终可以判断出两棵树是否相同。

2.代码实现

//判断两棵二叉树是否相同的函数
//参数 p 和 q 分别是两棵二叉树的根节点指针
bool isSameTree(struct TreeNode* p, struct TreeNode* q)
{//如果两棵树的当前节点都为空，说明这两个位置的结构是相同的，返回 trueif (p == NULL && q == NULL)return true;//如果其中一棵树的当前节点为空，而另一棵树的当前节点不为空，//这意味着两棵树的结构不同，返回 falseif (p == NULL || q == NULL)return false;//如果两棵树当前节点的值不相等，说明这两棵树不相同，返回 falseif (p->val != q->val)return false;//如果两棵树当前节点的值相等，则递归地判断两棵树的左子树和右子树是否相同//只有当左子树和右子树都相同时，才能认为这两棵树相同return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}

练习题3：翻转二叉树

LCR 144. 翻转二叉树 - 力扣（LeetCode）

1.翻转二叉树的思路

翻转二叉树整体思路说明：这段代码采用递归的方法来翻转二叉树。核心思路是遍历二叉树的每个节点，在遍历过程中交换每个节点的左右子树。对于空树（节点指针为 NULL），不进行任何操作直接返回 NULL。通过递归调用函数处理每个节点的左右子树，直至遍历完整个二叉树，最终实现整棵树的翻转。

思路总结：遍历每个结点，然后每个结点都要交换左右孩子。

2.代码实现

// 定义一个函数用于翻转二叉树，接收二叉树的根节点指针作为参数，返回翻转后二叉树的根节点指针
struct TreeNode* flipTree(struct TreeNode* root) 
{// 处理空树的情况：如果传入的根节点指针为 NULL，意味着当前是一棵空树// 空树无需进行翻转操作，直接返回 NULL 作为空树翻转后的结果if(root == NULL){return NULL;}// 交换当前节点的左右子树：// 定义一个临时指针变量 tmp，用于临时存储当前节点左子树的地址struct TreeNode* tmp = root->left;// 将当前节点右子树的地址赋值给左子树指针，使左子树指针指向原来的右子树root->left = root->right;// 把之前临时存储在 tmp 中的左子树地址赋值给右子树指针，完成左右子树的交换root->right = tmp;// 递归调用 flipTree 函数对当前节点的左子树进行翻转// 若左子树不为空，会继续交换左子树中每个节点的左右子树；若左子树为空（即 root->left 为 NULL），则会在递归时直接返回 NULLflipTree(root->left);// 递归调用 flipTree 函数对当前节点的右子树进行翻转// 若右子树不为空，会继续交换右子树中每个节点的左右子树；若右子树为空（即 root->right 为 NULL），则会在递归时直接返回 NULLflipTree(root->right);// 当当前节点及其所有子节点都完成左右子树的交换后，返回当前节点作为翻转后子树的根节点return root;
}

练习题4：对称二叉树

101. 对称二叉树 - 力扣（LeetCode）

1.判断二叉树是对称二叉树思路

对于一棵二叉树，如果它是对称的，那么它的左子树和右子树在结构和节点值上是镜像对称的。也就是说，左子树的左子节点与右子树的右子节点对应，左子树的右子节点与右子树的左子节点对应，并且对应节点的值相等。

2.代码实现

//子函数，用于递归判断两棵子树是否对称
//参数 root1 和 root2 分别是需要比较的两棵子树的根节点指针
bool _isSymmetric(struct TreeNode* root1, struct TreeNode* root2)
{//如果两棵子树的根节点都为空，说明这两棵子树在当前位置结构上是对称的//空树与空树是对称的，所以返回 trueif (root1 == NULL && root2 == NULL)return true;//如果其中一棵子树的根节点为空，而另一棵不为空//这表明两棵子树在结构上不对称，返回 falseif (root1 == NULL || root2 == NULL)return false;//如果两棵子树的根节点的值不相等//那么这两棵子树肯定不是对称的，返回 falseif (root1->val != root2->val)return false;//递归地比较 root1 的左子树和 root2 的右子树，以及 root1 的右子树和 root2 的左子树//只有当这两组子树都对称时，才能认为 root1 和 root2 所代表的两棵子树是对称的return _isSymmetric(root1->left, root2->right) && _isSymmetric(root1->right, root2->left);
}//判断整棵二叉树是否对称的主函数
//参数 root 是二叉树的根节点指针
bool isSymmetric(struct TreeNode* root)
{//如果根节点为空，空树被认为是对称的，直接返回 true//否则调用 _isSymmetric 子函数，比较根节点的左子树和右子树是否对称return !root || _isSymmetric(root->left, root->right);
}

3.其他思路

注意：下面的思路都是不好的，效率低，所以这里就不实现了。

3.1.思路 1：先拷贝原树创建新树，新树翻转，然后再和原树判断是否相等

(1)思路说明

拷贝原树：通过递归的方式遍历原树，为每个节点创建一个新的节点，从而得到一棵与原树结构和节点值都相同的新树。
翻转新树：递归地交换新树中每个节点的左右子节点，实现树的翻转。
比较原树和翻转后的新树：递归地比较原树和翻转后的新树的每个节点，如果所有节点都相等，则说明原树是对称的。

(2)复杂度分析

时间复杂度：O(N)，其中N是二叉树的节点数。需要遍历原树进行拷贝，遍历拷贝的树进行翻转，以及遍历两棵树进行比较，每个操作的时间复杂度都是O(N)。
空间复杂度：O(N)，主要是拷贝树所需的额外空间。

(3)缺陷

空间复杂度高：需要额外拷贝一棵完整的二叉树，这会占用与原树相同的额外空间，空间复杂度为，其中是二叉树的节点数。
操作步骤多：涉及树的拷贝、树的翻转以及两棵树的比较三个操作，增加了代码的复杂度和时间开销。

3.2.思路 2：先对原树的左子树进行翻转，然后再比较左右子树是否相等，最后恢复原树结构

(1)思路说明

翻转左子树：对原树的左子树进行翻转操作，交换左子树中每个节点的左右子节点。
比较左右子树：递归地比较翻转后的左子树和右子树的每个节点，如果所有节点都相等，则说明原树是对称的。
恢复原树结构：为了不改变原树的结构，可以再次翻转左子树，将其恢复到原来的状态。

(2)复杂度分析

时间复杂度：O(N)，需要遍历左子树进行翻转，以及遍历左右子树进行比较，每个操作的时间复杂度都是O(N)。
空间复杂度：O(h) = O(logN)，其中h是二叉树的高度，主要是递归调用栈的空间。但原树的结构会被修改。

(3)缺陷

修改原树结构：这种方法会改变原二叉树的结构，在某些场景下可能不被允许，因为调用者可能不希望原树被修改。
操作步骤多：需要先进行左子树的翻转操作，然后再进行左右子树的比较，相比直接递归判断对称，步骤更多，复杂度更高。

练习题5：另一颗树的子树

572. 另一棵树的子树 - 力扣（LeetCode）

1.分析

(1) 一颗树与另一颗树的子树完全相等

(2) 一颗树与另一颗树的子树局部相等

2.判断一棵树是另一棵树的子树的思路

`(1)isSameTree` 函数思路

整体思路：判断两棵树是否完全相同，需要从根节点开始，依次比较两棵树对应位置的节点。对于每一对对应节点，需要检查它们的值是否相等，以及它们的左子树和右子树是否也分别相同。这个过程可以通过递归的方式来实现。
具体步骤：
- 边界条件判断：
  - 如果两个节点都为空，说明在当前位置两棵树的结构是相同的，返回 true。
  - 如果其中一个节点为空，另一个不为空，说明两棵树的结构不同，返回 false。
- 节点值比较：如果两个节点都不为空，比较它们的值。如果值不相等，说明两棵树不相同，返回 false。
- 递归比较子树：如果当前节点的值相等，递归地比较它们的左子树和右子树。只有当左右子树都相同时，两棵树才相同。

`(2)isSubtree` 函数思路

整体思路：判断 subRoot 是否是 root 的子树，需要遍历 root 树的每个节点，对于 root 树中的每个节点，检查以该节点为根的子树是否和 subRoot 完全相同。这个过程可以通过递归的方式来实现。
具体步骤：
- 边界条件判断：如果 root 为空树，那么不可能存在子树，返回 false。
- 检查当前节点：使用 isSameTree 函数检查以 root 为根的树是否和 subRoot 完全相同。如果相同，则说明 subRoot 是 root 的子树，返回 true。
- 递归查找子树：如果以 root 为根的树和 subRoot 不同，则递归地在 root 的左子树和右子树中继续查找。只要在左子树或右子树中找到和 subRoot 相同的子树，就返回 true。如果都没有找到，则返回 false。

3.代码实现

// 判断两棵树是否完全相同
bool isSameTree(struct TreeNode* p, struct TreeNode* q) 
{//如果两棵树的当前节点都为空，说明在当前位置两棵树的结构是相同的，返回 trueif (p == NULL && q == NULL)return true;//如果其中一棵树的当前节点为空，而另一棵不为空，说明两棵树的结构不同，返回 falseif (p == NULL || q == NULL)return false;//如果两棵树当前节点的值不相等，说明这两棵树不相同，返回 falseif (p->val != q->val)return false;//递归地比较两棵树的左子树和右子树，只有当左右子树都相同时，两棵树才相同return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}//判断 subRoot 是否是 root 的子树
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot) 
{//如果 root 为空树，那么不可能存在子树，返回 falseif (root == NULL)return false;//检查以 root 为根的树是否和 subRoot 完全相同，如果相同则说明 subRoot 是 root 的子树if (isSameTree(root, subRoot))return true;//若当前以 root 为根的树和 subRoot 不同，则递归地在 root 的左子树和右子树中继续查找return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}

练习题6：二叉树的前序遍历

144. 二叉树的前序遍历 - 力扣（LeetCode）

1.代码实现

//计算二叉树的节点数量
int TreeSize(struct TreeNode* root)
{//如果当前节点为空，说明是空树，节点数量为 0//否则，递归计算左子树和右子树的节点数量，并加上当前节点（即 +1）return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}//前序遍历二叉树，并将节点值存储到数组 a 中
//参数 root 是当前遍历的子树的根节点
//参数 a 是用于存储节点值的数组
//参数 pi 是指向数组索引的指针，用于记录当前存储位置
void preorder(struct TreeNode* root, int* a, int* pi)
{//如果当前节点为空，说明到达空树，直接返回if(root == NULL)return;//将当前节点的值存储到数组 a 中，并将索引指针后移一位a[(*pi)++] = root->val;//递归遍历左子树preorder(root->left, a, pi);//递归遍历右子树preorder(root->right, a, pi);
}//前序遍历二叉树的主函数，返回存储前序遍历结果的数组
//参数 root 是二叉树的根节点
//参数 returnSize 是指向存储遍历结果数组长度的指针
int* preorderTraversal(struct TreeNode* root, int* returnSize)
{//计算二叉树的节点数量，并将其赋值给 returnSize 所指向的变量*returnSize = TreeSize(root);//动态分配内存，用于存储前序遍历的结果，大小为节点数量乘以 int 类型的大小int* a = (int*)malloc(*returnSize * sizeof(int));//初始化数组索引为 0int i = 0;//调用 preorder 函数进行前序遍历，将结果存储到数组 a 中preorder(root, a, &i);//返回存储前序遍历结果的数组return a;
}

2.代码分析

整个代码的目的是实现二叉树的前序遍历，并将遍历结果存储在一个动态分配的数组中返回。具体步骤如下：

计算节点数量：调用 TreeSize 函数计算二叉树的节点数量，以便确定存储遍历结果的数组的大小。
动态分配内存：根据节点数量，使用 malloc 函数动态分配一个大小合适的数组，用于存储前序遍历的结果。
前序遍历：调用 preorder 函数进行前序遍历，将遍历过程中访问到的节点值依次存储到数组中。
返回结果：返回存储前序遍历结果的数组，并通过 returnSize 指针返回数组的长度。

3.错误写法

(1)这种错误写法只是恰好对下面这个测试用例没有影响而已。

(2)这种错误写法一定会对下面这个测试用例造成影响的。

练习题7：二叉树的中序遍历

94. 二叉树的中序遍历 - 力扣（LeetCode）

1.代码实现

//计算二叉树的节点数量
int TreeSize(struct TreeNode* root)
{//如果当前节点为空，说明是空树，节点数量为 0//否则，递归计算左子树和右子树的节点数量，并加上当前节点（即 +1）return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}//中序遍历二叉树，并将节点值存储到数组 a 中
//参数 root 是当前遍历的子树的根节点
//参数 a 是用于存储节点值的数组
//参数 pi 是指向数组索引的指针，用于记录当前存储位置
void inorder(struct TreeNode* root, int* a, int* pi)
{// 如果当前节点为空，说明到达空树，直接返回if (root == NULL)return;// 递归遍历左子树inorder(root->left, a, pi);// 将当前节点的值存储到数组 a 中，并将索引指针后移一位a[(*pi)++] = root->val;// 递归遍历右子树inorder(root->right, a, pi);
}//中序遍历二叉树的主函数，返回存储中序遍历结果的数组
//参数 root 是二叉树的根节点
//参数 returnSize 是指向存储遍历结果数组长度的指针
int* inorderTraversal(struct TreeNode* root, int* returnSize) 
{//计算二叉树的节点数量，并将其赋值给 returnSize 所指向的变量*returnSize = TreeSize(root);//动态分配内存，用于存储中序遍历的结果，大小为节点数量乘以 int 类型的大小int* a = (int*)malloc(*returnSize * sizeof(int));//初始化数组索引为 0int i = 0;//调用 inorder 函数进行中序遍历，将结果存储到数组 a 中inorder(root, a, &i);//返回存储中序遍历结果的数组return a;
}

练习题8：二叉树的后序遍历

145. 二叉树的后序遍历 - 力扣（LeetCode）

1.代码实现

//计算二叉树的节点数量
int TreeSize(struct TreeNode* root)
{//如果当前节点为空，说明是空树，节点数量为 0//否则，递归计算左子树和右子树的节点数量，并加上当前节点（即 +1）return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}//后序遍历二叉树，并将节点值存储到数组 a 中
//参数 root 是当前遍历的子树的根节点
//参数 a 是用于存储节点值的数组
//参数 pi 是指向数组索引的指针，用于记录当前存储位置
void postorder(struct TreeNode* root, int* a, int* pi)
{//如果当前节点为空，说明到达空树，直接返回if (root == NULL)return;//递归遍历左子树postorder(root->left, a, pi);//递归遍历右子树postorder(root->right, a, pi);//将当前节点的值存储到数组 a 中，并将索引指针后移一位a[(*pi)++] = root->val;
}//后序遍历二叉树的主函数，返回存储后序遍历结果的数组
//参数 root 是二叉树的根节点
//参数 returnSize 是指向存储遍历结果数组长度的指针
int* postorderTraversal(struct TreeNode* root, int* returnSize) 
{//计算二叉树的节点数量，并将其赋值给 returnSize 所指向的变量*returnSize = TreeSize(root);//动态分配内存，用于存储后序遍历的结果，大小为节点数量乘以 int 类型的大小int* a = (int*)malloc(*returnSize * sizeof(int));//初始化数组索引为 0int i = 0;//调用 postorder 函数进行后序遍历，将结果存储到数组 a 中postorder(root, a, &i);//返回存储后序遍历结果的数组return a;
}

练习题9：二叉树的构建及遍历

利用前序遍历创建二叉树rebuildTree

二叉树遍历_牛客题霸_牛客网

1.思路

利用前序遍历创建整个链式二叉树的思路分成以下3个步骤：

创建当前树的根结点空间
创建当前树的左子树空间(递归构建左子树)并与当前树的根结点进行链接
创建当前树的右子树空间(递归构建右子树)并与当前树的根结点进行链接

注意：要想利用题目给的前序遍历字符串创建一个二叉树的话，则这个二叉树的创建必须按前序遍历的思路进行创建。

2.代码实现

注意：在递归实现rebuildTree函数构成二叉树时，一定要传下标 i 的地址给rebuildTree函数，而不是直接传 i 的值，因为形参是实参的临时拷贝，要想通过形参改变实参的话则必须传 i 的地址。

#include <stdio.h>
#include <stdlib.h>//定义树节点结构
struct TreeNode 
{char val;struct TreeNode* left;//指向左孩子struct TreeNode* right;//指向右孩子
};//创建二叉树
struct TreeNode* rebuildTree(char* str, int* pi) 
{//若遍历字符串时，str[*pi]遇到‘#’字符时就表示当前要构建的二叉树是个空树即要构建的根结点是个//空结点，所以此时返回NULL表示不需要用‘#’字符符创建空结点，同时(*pi)++让字符串的下一个字符//为创建下一个子树的根结点做准备。if (str[*pi] == '#') {(*pi)++;return NULL;}//创建当前树的根结点并完成初始化struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));//开空间root->val = str[(*pi)++];//初始化//递归构建左子树，并与当前树的根结点进行链接root->left = rebuildTree(str, pi);//递归构建右子树，并与当前树的根结点进行链接root->right = rebuildTree(str, pi);//返回构建完的当前树的根结点return root;
}//中序遍历
void InOrder(struct TreeNode* root)
{//若指针root指向的当前树(子树)是空树(NULL)，则当前树的根结点是个空结点(NULL)，则此时打印 //NULL表示当前树的中序遍历结束了。if (root == NULL){return;}InOrder(root->left);//先访问当前树的左子树printf("%c ", root->val);//再访问当前树根结点的值InOrder(root->right);//后访问当前树的右子树
}//销毁链式二叉树
void TreeDestroy(struct TreeNode* root)
{if (root == NULL)return;TreeDestroy(root->left);//先销毁左子树TreeDestroy(root->right);//再销毁右子树//最后销毁当前树的根结点free(root);
}int main() 
{//输入一串先序遍历字符串，并用字符数组str存储起来char str[100];//测试用例：字符串"abc##de#g##f###"，其中字'#'表示的是空格，空格字符代表空树。scanf("%s", str);//利用前序遍历创建链式二叉树int i = 0;struct TreeNode* root = rebuildTree(str, &i);//中序遍历InOrder(root);//销毁链式二叉树TreeDestroy(root);return 0;
}

3.利用前序序列创建二叉树的代码分析

(1)前序遍历序列的特点

前序遍历的顺序是 “根 - 左 - 右”，即先访问根节点，然后递归访问左子树，最后递归访问右子树。在这个问题中，使用 # 来表示空节点。

(2)创建二叉树rebuildTree函数实现的具体步骤

读取当前字符：从输入的前序遍历序列中读取当前字符。
判断是否为空节点：如果当前字符是 #，说明该位置为空节点，将索引后移一位，并返回 NULL。
创建根节点：如果当前字符不是 #，为该字符创建一个新的节点，并将其作为当前子树的根节点。
递归构建左子树：继续从序列中读取字符，递归调用 rebuildTree 函数构建左子树。
递归构建右子树：在左子树构建完成后，继续从序列中读取字符，递归调用 rebuildTree 函数构建右子树。
返回根节点：返回构建好的根节点。

(3)整体思路是通过递归的方式，根据输入的前序遍历序列逐步构建二叉树。具体流程如下：

输入前序遍历序列：在 main 函数中，从标准输入读取包含 # 表示空节点的前序遍历序列。
重建二叉树：调用 rebuildTree 函数，从序列的第一个字符开始处理。根据字符是否为 # 来判断节点是否为空，递归地构建左子树和右子树。
中序遍历验证：调用 InOrder 函数对重建后的二叉树进行中序遍历，并打印节点值，以此验证二叉树是否构建正确。
释放内存：调用 TreeDestroy 函数，使用后序遍历的方式销毁二叉树，释放所有节点占用的内存，避免内存泄漏。

4.错误写法

4.1.错误代码

4.2.错误分析

(1)错误原因

rebulidTree函数的形参下标i只是个局部变量而rebulidTree是个递归函数，由于形参i只是实参的临时拷贝，所以在不断递归调用rebulidTree函数时每个rebulidTree函数中的i++都不是增加同一个i的值。

(2)错误代码的递归过程

练习题10：根据前序和中序序列创建二叉树

1.根据后序和中序序列创建二叉树的思路

(1)前序和中序遍历的特性

前序遍历：遍历顺序为 “根 - 左 - 右”，所以前序遍历序列的第一个元素就是二叉树的根节点。
中序遍历：遍历顺序为 “左 - 根 - 右”，在中序遍历序列中，根节点将序列分为左右两部分，左边部分是左子树的中序遍历序列，右边部分是右子树的中序遍历序列。

(2)具体步骤

①确定根节点：从前序遍历序列中取出第一个元素，这个元素就是当前子树的根节点。

②找到根节点在中序遍历序列中的位置：通过遍历中序遍历序列，找到根节点的位置。这个位置将中序遍历序列分为左子树的中序遍历序列和右子树的中序遍历序列。

③计算左右子树的节点数量：根据根节点在中序遍历序列中的位置，计算左子树和右子树的节点数量。左子树的节点数量等于根节点在中序遍历序列中的位置索引；右子树的节点数量等于中序遍历序列的总长度减去左子树节点数量再减去 1（根节点）。

④递归构建左右子树：

对于左子树，从前序遍历序列中取出根节点之后长度为左子树节点数量的部分作为左子树的前序遍历序列，从中序遍历序列中取出开头到根节点位置之前的部分作为左子树的中序遍历序列，然后递归调用 buildTree 函数构建左子树。
对于右子树，从前序遍历序列中取出左子树节点之后的部分作为右子树的前序遍历序列，从中序遍历序列中取出根节点位置之后的部分作为右子树的中序遍历序列，递归调用 buildTree 函数构建右子树。

(3)整体思路

整体思路就是利用前序遍历和中序遍历的特性，通过递归的方式不断确定根节点，并构建左右子树。具体来说，从前序遍历序列中确定根节点，然后在中序遍历序列中找到根节点的位置，划分出左右子树的中序遍历序列，再根据左右子树的节点数量划分出左右子树的前序遍历序列，最后递归构建左右子树，直到所有节点都被处理完。在 main 函数中，我们定义了前序和中序遍历序列，调用 buildTree 函数构建二叉树，然后使用前序遍历打印重建后的二叉树，验证构建的正确性，最后销毁二叉树，释放内存。

2.代码实现

#include <stdio.h>
#include <stdlib.h>// 定义二叉树节点结构体
typedef struct TreeNode
{int val;  //节点存储的值struct TreeNode* left;  //指向左子节点的指针struct TreeNode* right; //指向右子节点的指针
} TreeNode;//创建一个新的二叉树节点
TreeNode* createNode(int value)
{//为新节点分配内存TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));//若内存分配失败，返回 NULLif (!newNode) return NULL;//为新节点赋值newNode->val = value;//初始化新节点的左右子节点为空newNode->left = newNode->right = NULL;return newNode;
}// 根据前序遍历和中序遍历序列构建二叉树
TreeNode* buildTree(int* preorder, int* inorder, int preordersize, int inordersize)
{//若前序或中序序列为空，说明该子树为空，返回 NULLif (preordersize == 0 || inordersize == 0)return NULL;//前序遍历的第一个元素是当前子树的根节点的值，创建根节点TreeNode* root = createNode(preorder[0]);int rootIndex = 0;//在中序遍历序列中找到根节点的位置while (inorder[rootIndex] != preorder[0]) rootIndex++;//递归构建左子树//前序遍历中，左子树的节点从根节点之后开始，长度为 rootIndex//中序遍历中，左子树的节点从开头到根节点位置之前，长度为 rootIndexroot->left = buildTree(preorder + 1, inorder, rootIndex, rootIndex);//递归构建右子树//前序遍历中，右子树的节点从左子树节点之后开始，长度为 preordersize - rootIndex - 1//中序遍历中，右子树的节点从根节点位置之后开始，长度为 inordersize - rootIndex - 1root->right = buildTree(preorder + rootIndex + 1, inorder + rootIndex + 1, preordersize - rootIndex - 1, inordersize - rootIndex - 1);return root;
}//前序遍历打印二叉树节点的值
void printPreorder(TreeNode* root)
{//若当前节点为空，直接返回if (root == NULL) return;//打印当前节点的值printf("%d ", root->val);//递归打印左子树printPreorder(root->left);//递归打印右子树printPreorder(root->right);
}//二叉树销毁函数，利用后序遍历来销毁二叉树
void TreeDestroy(TreeNode* root)
{//若当前节点为空，直接返回if (root == NULL)return;//先递归销毁左子树TreeDestroy(root->left);//再递归销毁右子树TreeDestroy(root->right);//最后释放当前节点的内存free(root);
}int main()
{//定义前序遍历序列int preorder[] = { 3, 9, 20, 15, 7 };//定义中序遍历序列int inorder[] = { 9, 3, 15, 20, 7 };//计算前序遍历序列的长度int preordersize = sizeof(preorder) / sizeof(preorder[0]);//计算中序遍历序列的长度int inordersize = sizeof(inorder) / sizeof(inorder[0]);//根据前序和中序序列构建二叉树TreeNode* root = buildTree(preorder, inorder, preordersize, inordersize);//前序遍历打印构建好的二叉树printPreorder(root);//销毁构建好的二叉树，释放内存TreeDestroy(root);return 0;
}

3.根据前序和中序序列创建二叉树的过程及图形解析

没开始重建二叉树的图形解析：

①通过前序序列确定根1，然后通过中序序列确定根1的左边(3、2)是左子树而根1的右边(5、4、6)是右子树，再构建根1的左子树和右子树。

图形解析：

②通过前序序列确定根2，然后通过中序序列确定根2的左边(3)是左子树而根2的右边(空)是右子树，由于根2的右边是空树所以只需构建根2的左子树。

图形解析：

③通过前序序列确定根3，然后通过中序序列确定根3的左边(空)是空左子树而根3的右边(空)是空右子树，由于根3的左右子树都是空树则此时不用构建根3的左右子树。

图形解析：

④通过前序序列确定根4，然后通过中序序列确定根4的左边(5)是左子树而根4的右边(6)是右子树，再构建根4左子树和右子树。

图形解析：

⑤通过前序序列确定根5，然后通过中序序列确定根5的左边(空)是空左子树而根5的右边(空)是空右子树，由于根5的左右子树都是空树则此时不用构建根5的左右子树。

图形解析：

⑥通过前序序列确定根6，然后通过中序序列确定根5的左边(空)是空左子树而根6的右边(空)是空右子树，由于根6的左右子树都是空树则此时不用构建根6的左右子树。

图形解析：

⑦最终得出的创建后的二叉树：

图形解析：

总的来说，通过前序序列确定二叉树每个子树的根，然后再通过中序遍历去构建前序序列中每个根的左右子树。

4.总结

(1)根据前序和中序序列创建二叉树的思路：通过前序确定根，通过中序分割出左右子树。

(2)前序序列中的每个数都是子树的根，中序序列是用来确定每个子树根的左右子树。

(3)注意事项：利用前序序列和中序序列创建二叉树时是有限制的，即这个限制指的是这个树是不能有数据值相同的结点。

练习题11：根据后序和中序序列创建二叉树

1.根据后序和中序序列创建二叉树的思路

(1)后序和中序遍历的特性

后序遍历：顺序是 “左 - 右 - 根”，所以后序遍历序列的最后一个元素就是二叉树的根节点。
中序遍历：顺序是 “左 - 根 - 右”，在中序遍历序列中，根节点将序列分为左右两部分，左边部分是左子树的中序遍历序列，右边部分是右子树的中序遍历序列。

(2)具体步骤

①确定根节点：从后序遍历序列中取出最后一个元素，这个元素就是当前子树的根节点。

③计算左右子树的节点数量：根据根节点在中序遍历序列中的位置，计算左子树和右子树的节点数量。

④递归构建左右子树：

对于左子树，根据左子树的节点数量，从后序遍历序列和中序遍历序列中提取出左子树的后序遍历序列和中序遍历序列，然后递归调用 buildTree 函数构建左子树。
对于右子树，同理，从后序遍历序列和中序遍历序列中提取出右子树的后序遍历序列和中序遍历序列，递归调用 buildTree 函数构建右子树。

(3)整体思路

整体思路就是利用后序遍历和中序遍历的特性，通过递归的方式不断确定根节点，并构建左右子树。具体来说，从后序遍历序列中确定根节点，然后在中序遍历序列中找到根节点的位置，划分出左右子树的中序遍历序列，再根据左右子树的节点数量划分出左右子树的后序遍历序列，最后递归构建左右子树，直到所有节点都被处理完。在 main 函数中，我们定义了后序和中序遍历序列，调用 buildTree 函数构建二叉树，然后使用后序遍历打印重建后的二叉树，验证构建的正确性，最后销毁二叉树，释放内存。

2.代码实现

#include <stdio.h>
#include <stdlib.h>//定义二叉树节点结构
typedef struct TreeNode 
{int val;struct TreeNode* left;struct TreeNode* right;
}TreeNode;//创建一个新的二叉树节点
TreeNode* createNode(int value) 
{//为新节点分配内存TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));//如果内存分配失败，返回 NULLif (!newNode) return NULL;//设置新节点的值newNode->val = value;//初始化新节点的左右子节点为 NULLnewNode->left = newNode->right = NULL;return newNode;
}//根据后序遍历和中序遍历序列构建二叉树
TreeNode* buildTree(int* postorder, int* inorder, int postordersize, int inordersize) 
{//如果后序遍历序列或中序遍历序列为空，说明没有节点，返回 NULLif (postordersize == 0 || inordersize == 0)return NULL;//后序遍历的最后一个元素是根节点的值TreeNode* root = createNode(postorder[postordersize - 1]);int rootIndex;//在中序遍历序列中找到根节点的位置for (rootIndex = 0; rootIndex < inordersize; rootIndex++) {if (inorder[rootIndex] == postorder[postordersize - 1]) break;}//计算左子树的中序遍历序列的长度int leftInorderSize = rootIndex;//计算右子树的中序遍历序列的长度int rightInorderSize = inordersize - rootIndex - 1;// 递归构建左子树root->left = buildTree(postorder, inorder, leftInorderSize, leftInorderSize);// 递归构建右子树root->right = buildTree(postorder + leftInorderSize, inorder + leftInorderSize + 1, rightInorderSize, rightInorderSize);return root;
}//后序遍历打印二叉树节点值
void printPostorder(TreeNode* root) 
{//如果当前节点为空，直接返回if (root == NULL) return;//递归遍历左子树printPostorder(root->left);//递归遍历右子树printPostorder(root->right);//打印当前节点的值printf("%d ", root->val);
}//二叉树销毁函数(利用后序遍历来销毁二叉树)
void TreeDestroy(TreeNode* root)
{if (root == NULL)return;//后序遍历TreeDestroy(root->left);//先销毁左子树TreeDestroy(root->right);//再销毁右子树//最后销毁当前树的根结点free(root);
}int main() 
{//定义中序遍历序列int inorder[] = { 9, 3, 15, 20, 7 };//定义后序遍历序列int postorder[] = { 9, 15, 7, 20, 3 };//计算后序遍历序列的长度int postordersize = sizeof(postorder) / sizeof(postorder[0]);//计算中序遍历序列的长度int inordersize = sizeof(inorder) / sizeof(inorder[0]);//根据后序和中序遍历序列构建二叉树TreeNode* root = buildTree(postorder, inorder, postordersize, inordersize);//后序遍历打印重建后的二叉树printPostorder(root);//销毁构建好的二叉树，释放内存TreeDestroy(root);return 0;
}