代码解决：
咱们还可以不修改输入树的结构，使用前序遍历，代码如下：
struct TreeNode* mergeTrees(struct TreeNode* t1, struct TreeNode* t2) { if (t1 == NULL) return t2; if (t2 == NULL) return t1; // 重新定义新的节点，不修改原有两个树的结构 struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode)); root->val = t1->val + t2->val; root->left = mergeTrees(t1->left, t2->left); root->right = mergeTrees(t1->right, t2->right); return root; }
测试结果：
最大二叉树
题目来源：Leetcode654.最大二叉树
题目描述：
给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:
创建一个根节点，其值为 nums 中的最大值。
1.递归地在最大值 左边 的 子数组前缀上 构建左子树。
2.递归地在最大值 右边 的 子数组后缀上 构建右子树。
3.返回 nums 构建的 最大二叉树 。
解题思路：
1、以左闭右开为区间递归构造二叉树，区间内至少得有一个元素，
若left >= right则表示无节点，需返回NULL
2、找到当前区间中最大的元素，记录下标maxValueIndex
3、以[left, maxIndex) 和 [maxIndex + 1, right)为区间构造左右子树
代码解决：
struct TreeNode* traversal(int* nums, int left, int right) { //若左边界大于右边界，返回NULL if(left >= right) return NULL; //找出数组中最大数坐标 int maxIndex = left; int i; for(i = left + 1; i < right; i++) { if(nums[i] > nums[maxIndex]) maxIndex = i; } //开辟结点 struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode)); //将结点的值设为最大数组数组元素 node->val = nums[maxIndex]; node->left=NULL; node->right=NULL; //递归定义左孩子结点和右孩子结点 node->left = traversal(nums, left, maxIndex); node->right = traversal(nums, maxIndex + 1, right); return node; } struct TreeNode* constructMaximumBinaryTree(int* nums, int numsSize) { return traversal(nums, 0, numsSize); }
总结：
费尽千辛万苦，咱们链式二叉树已经圆满结束了，希望本篇文章能对你有所帮助。
以下是测试所用的代码：
头文件.h
#include<stdio.h> #include<stdlib.h> #include<assert.h> #include<stdbool.h> #include<stdio.h> #include<stdlib.h> #include<assert.h> #include<stdbool.h> typedef struct BinaryTreeNode* QDataType; typedef struct QueueNode { struct QueueNode* next; QDataType data; }QNode; typedef struct Queue { QNode* head; QNode* tail; int size; }Que; void QueueInit(Que* pq); void QueueDestroy(Que* pq); void QueuePush(Que* pq, QDataType x); void QueuePop(Que* pq); QDataType QueueFront(Que* pq); QDataType QueueBack(Que* pq); bool QueueEmpty(Que* pq); int QueueSize(Que* pq);
源文件1（Queue.c）
#include "Queue.h" void QueueInit(Que* pq) { assert(pq); pq->head = pq->tail = NULL; pq->size = 0; } void QueueDestroy(Que* pq) { assert(pq); QNode* cur = pq->head; while (cur) { QNode* next = cur->next; free(cur); cur = next; } pq->head = pq->tail = NULL; pq->size = 0; } void QueuePush(Que* pq, QDataType x) { assert(pq); QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { perror("malloc fail"); exit(-1); } newnode->data = x; newnode->next = NULL; if (pq->tail == NULL) { pq->head = pq->tail = newnode; } else { pq->tail->next = newnode; pq->tail = newnode; } pq->size++; } void QueuePop(Que* pq) { assert(pq); assert(!QueueEmpty(pq)); if (pq->head->next == NULL) { free(pq->head); pq->head = pq->tail = NULL; } else { QNode* next = pq->head->next; free(pq->head); pq->head = next; } pq->size--; } QDataType QueueFront(Que* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->head->data; } QDataType QueueBack(Que* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->tail->data; } bool QueueEmpty(Que* pq) { assert(pq); return pq->head == NULL; } int QueueSize(Que* pq) { assert(pq); return pq->size; }
源文件2（BinaryTree.c）
#define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> #include<stdlib.h> #include<assert.h> #include<stdbool.h> typedef struct BinaryTreeNode { struct BinaryTreeNode* left; struct BinaryTreeNode* right; int val; }BTNode; #include"Queue.h" //开辟节点 BTNode* BuyNode(int x) { BTNode* node = (BTNode*)malloc(sizeof(BTNode)); if (node == NULL) { printf("malloc fail"); exit(-1); } node->val = x; node->left = NULL; node->right = NULL; } //前序遍历 void PrevOrder(BTNode* root) { if (root == NULL) { return; } printf("%d ", root->val); PrevOrder(root->left); PrevOrder(root->right); } //中序遍历 void InOrder(BTNode* root) { if (root == NULL) { return; } PrevOrder(root->left); printf("%d ", root->val); PrevOrder(root->right); } //后序遍历 void PostOrder(BTNode* root) { if (root == NULL) { return; } PrevOrder(root->left); PrevOrder(root->right); printf("%d ", root->val); } //层序遍历 void LevelOrder(BTNode* root) { Que q; QueueInit(&q);//初始化队列 if (root) QueuePush(&q, root); //队列不为空。循环继续 while (!QueueEmpty(&q)) { //获取队头元素 BTNode* front = QueueFront(&q); printf("%d ", front->val); //出队元素的左孩子入队列 if (front->left) QueuePush(&q, front->left); //出队元素的右孩子入队列 if (front->right) QueuePush(&q, front->right); QueuePop(&q); } printf("\n"); //销毁队列 QueueDestroy(&q); } //树节点的个数 int BinaryTreeSize(BTNode* root) { //节点个数=左子树的节点个数+右子树的节点个数+1; return root == NULL ? 0 : BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1; } //叶子节点的个数 int BinaryTreeLeafSize(BTNode* root) { //空树无叶子节点 if (root == NULL) { return 0; } //是叶子节点 if (root->left == NULL && root->right == NULL) { return 1; } //叶子节点个数=左子树的节点个数+右子树的节点个数 return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right); } //左叶子之和 int sumOfLeftLeaves(BTNode* root) { //空树叶子无节点 if (root == NULL) { return 0; } int sum = 0; //判断是否为左叶子节点 if (root->left && root->left->left == NULL && root->left->right == NULL) { sum = root->left->val; } return sum + sumOfLeftLeaves(root->left) + sumOfLeftLeaves(root->right); } //树中第K层节点个数为： int BinaryTreeKLeveSize(BTNode* root,int k) { //空树或输入不合法 if (k < 1 || root == NULL) { return 0; } //K=1为第一层 if (k == 1) { return 1; } //第K层的节点个数=相对于两个孩子的第K-1层的节点个数之和 return BinaryTreeKLeveSize(root->left, k - 1) + BinaryTreeKLeveSize(root->right, k - 1); } // 二叉树销毁 void TreeDestroy(BTNode* root) { if (root == NULL) { return; } TreeDestroy(root->left); TreeDestroy(root->right); free(root); //root = NULL; } // 二叉树查找值为x的结点 BTNode* TreeFind(BTNode* root, int x) { //空树 if (root == NULL) return NULL; //先判断根节点 if (root->val == x) return root; //在左孩子中找 BTNode* ret = NULL; ret = TreeFind(root->left, x); if (ret) return ret; //在右孩子中找 ret = TreeFind(root->right, x); if (ret) return ret; //根节点和左右子树节点中均未找到 return NULL; } // 判断二叉树是否是完全二叉树 int TreeComplete(BTNode* root) { Que q; QueueInit(&q);//初始化队列 if (root) QueuePush(&q, root); //当队列不为空时，继续 while (!QueueEmpty(&q)) { //读取队头元素 BTNode* front = QueueFront(&q); //当读取到空指针时，停止入队操作 if (front == NULL) break; //出队元素的左孩子入队列 QueuePush(&q, front->left); //出队元素的右孩子入队列 QueuePush(&q, front->right); QueuePop(&q); } // 已经遇到空节点，如果队列中后面的节点还有非空，就不是完全二叉树 while (!QueueEmpty(&q)) { BTNode* front = QueueFront(&q); QueuePop(&q); //若队列中存在非空指针，则不是完全二叉树 if (front != NULL) { //销毁队列 QueueDestroy(&q); return false; } } QueueDestroy(&q); //若队列中全是空指针，则是完全二叉树 return true; } //求树的深度或者高度 // //第一种写法：及其不推荐 //int TreeHeight(BTNode* root) //{ // if (root == NULL) // return 0; // // return TreeHeight(root->left) > TreeHeight(root->right) // ? TreeHeight(root->left) + 1 : TreeHeight(root->right) + 1; //} //树的深度：左右子树高的那颗树高度在加1 int TreeHeight(BTNode* root) { if (root == NULL) return 0; int leftHeight = TreeHeight(root->left); int rightHeight = TreeHeight(root->right); return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1; } //int TreeHeight(BTNode* root) //{ // if (root == NULL) // return 0; // // return fmax(TreeHeight(root->left), TreeHeight(root->right)) + 1; //} //求最大深度： int getdepth(BTNode* node) { if (node == NULL) return 0; int leftdepth = getdepth(node->left); // 左 int rightdepth = getdepth(node->right); // 右 int depth = 1 + max(leftdepth, rightdepth); // 中 return depth; } int maxDepth(BTNode* root) { return getdepth(root); } //求N叉树的最大深度 //int maxDepth(BTNode* root) //{ // if (root == NULL) // return 0; // int depth = 0; // for (int i = 0; i < root->numChildren; i++) // { // depth = fmax(depth, maxDepth(root->children[i])); // } // return depth + 1; //} //求最小深度 int getdepth2(BTNode* root) { if (root == NULL) return 0; int leftdepth = getdepth2(root->left);//左 int rightdepth = getdepth2(root->right);//右 //当左子树为空，右子树不为空，则此时并不是最低点 if (root->left == NULL && root->right != NULL) { return 1 + rightdepth; } //当左子树不为空，右子树为空，则此时并不是最低点 if (root->left != NULL && root->right == NULL) { return 1 + leftdepth; } //都不为空： int result = 1 + min(leftdepth, rightdepth); return result; } //int minDepth(struct TreeNode* root) //{ // return getdepth2(root); //} //精简版本： int minDepth(BTNode* root) { if (root == NULL) { return 0; } //左子树为空，右子树不为空 if (root->left == NULL && root->right != NULL) { return 1 + minDepth(root->right); } //左子树不为空，右子树为空 if (root->left != NULL && root->right == NULL) { return 1 + minDepth(root->left); } //都不为空： return min(minDepth(root->left), minDepth(root->right)) + 1; } //路径总和（是否存在路径和为目标值的路径，存在返回true,不存在返回false) bool hasPathSum(BTNode* root, int targetSum) { //空树时，不存在 if (root == NULL) { return false; } targetSum = targetSum - root->val; //左右节点均为空时，且targetSum为0时，满足条件 if (root->left == NULL && root->right == NULL && targetSum == 0) { return true; } // return hasPathSum(root->left, targetSum) || hasPathSum(root->right, targetSum); } //求树最左下角的值： void dfs(BTNode* root, int* max_depth, int depth, int* value) { if (root == NULL) { return; } if (*max_depth < depth) { *value = root->val; *max_depth = depth; } /* 保证深度最深的第一个点是左子树节点 */ dfs(root->left, max_depth, depth + 1, value); dfs(root->right, max_depth, depth + 1, value); } int findBottomLeftValue(BTNode* root) { if (root->right == NULL && root->left == NULL) { return root->val; } int value = 0; /* 记录最大深度 */ int max_depth = 0; dfs(root, &max_depth, 0, &value); return value; } //翻转二叉树 BTNode* invertTree(BTNode* root) { if (root == NULL)//根为空，直接返回 return NULL; BTNode* left = invertTree(root->left);//翻转左子树 BTNode* right = invertTree(root->right);//翻转右子树 //左右子树位置交换 root->left = right; root->right = left; return root; } //判断二叉树是否是平衡二叉树 bool isBalanced(BTNode* root) { if (root == NULL)//空树是平衡二叉树 return true; int leftDepth = TreeHeight(root->left);//求左子树的深度 int rightDepth = TreeHeight(root->right);//求右子树的深度 //左右子树高度差的绝对值不超过1 && 其左子树是平衡二叉树 && 其右子树是平衡二叉树 return abs(leftDepth - rightDepth) < 2 && isBalanced(root->left) && isBalanced(root->right); } //单值二叉树 bool isUnivalTree(BTNode* root) { //空树符合情况，返回true if (root == NULL) { return true; } //首先满足左子树不为空的条件下，判断左子树的值是否与根相同 if (root->left && root->left->val != root->val) { return false; } //首先满足右子树不为空的条件下，判断左子树的值是否与根相同 if (root->right && root->right->val != root->val) { return false; } return isUnivalTree(root->left) && isUnivalTree(root->right); } //相同的树 bool isSameTree(BTNode* p,BTNode* q) { //都为空 if (p == NULL && q == NULL) { return true; } //其中一个为空 if (p == NULL || q == NULL) { return false; } //都不为空 if (p->val != q->val) { return false; } return isSameTree(p->left, q->left) && isSameTree(p->right, q->right); } //对称二叉树： bool isSameTree2(BTNode* p, BTNode* q) { //都为空 if (p == NULL && q == NULL) { return true; } //其中一个为空 if (p == NULL || q == NULL) { return false; } //都不为空 if (p->val != q->val) { return false; } return isSameTree2(p->left, q->right) && isSameTree2(p->right, q->left); } bool isSymmetric(BTNode* root) { if (root == NULL) { return true; } return isSameTree2(root->left, root->right); } //二叉树的前序遍历（接口型） //为防止开辟空间浪费，先求一下树的节点个数 int TreeSize(BTNode* root) { return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1; } void preorder(BTNode* root, int* a, int* pi) { if (root == NULL) { return; } a[(*pi)++] = root->val; preorder(root->left, a, pi); preorder(root->right, a, pi); } int* preorderTraversal(BTNode* root, int* returnSize) { int n = TreeSize(root); int* a = (int*)malloc(sizeof(int) * n); int j = 0; preorder(root, a, &j); *returnSize = n; return a; } //另一颗树的子树 bool isSubtree(BTNode* root, BTNode* subRoot) { if (root == NULL) { return false; } if (root->val == subRoot->val) { if (isSameTree(root, subRoot)) { return true; } } return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot); } //二叉树遍历：（KY11牛客网） //#include <stdio.h> //#include<stdlib.h> // //typedef struct BinaryTreeNode //{ // struct BinaryTreeNode* left; // struct BinaryTreeNode* right; // int val; //}BTNode; // //BTNode* GreateTree(char* str, int* pi) //{ // if (str[*pi] == '#') // { // (*pi)++; // return NULL; // } // // BTNode* root = (BTNode*)malloc(sizeof(BTNode)); // root->val = str[*pi]; // (*pi)++; // // root->left = GreateTree(str, pi); // root->right = GreateTree(str, pi); // // return root; //} // //void Inorder(BTNode* root) //{ // if (root == NULL) // { // return; // } // // Inorder(root->left); // printf("%c ", root->val); // Inorder(root->right); // //} //int main() //{ // char str[100]; // scanf("%s", str); // // int i = 0; // BTNode* root = GreateTree(str, &i); // Inorder(root); // return 0; //} //完全二叉树的节点个数 int countNodes(BTNode* root) { if (root == NULL) { return 0; } //拿到左子树的个数 int lson = countNodes(root->left); //拿到右子树的个数 int rson = countNodes(root->right); //在加上自己 return 1 + lson + rson; } //合并二叉树： BTNode* mergeTrees(BTNode* t1, BTNode* t2) { if (t1 == NULL) return t2; if (t2 == NULL) return t1; // 重新定义新的节点，不修改原有两个树的结构 BTNode* root = (BTNode*)malloc(sizeof(BTNode)); if (root == NULL) { printf("malloc fail"); exit(-1); } root->val = t1->val + t2->val; root->left = mergeTrees(t1->left, t2->left); root->right = mergeTrees(t1->right, t2->right); //打印结果： Que q; QueueInit(&q);//初始化队列 if (root) QueuePush(&q, root); //队列不为空。循环继续 while (!QueueEmpty(&q)) { //获取队头元素 BTNode* front = QueueFront(&q); printf("%d ", front->val); //出队元素的左孩子入队列 if (front->left) QueuePush(&q, front->left); //出队元素的右孩子入队列 if (front->right) QueuePush(&q, front->right); QueuePop(&q); } //销毁队列 QueueDestroy(&q); return root; } //构建最大二叉树 //子函数 BTNode* traversal(int* nums, int left, int right) { //若左边界大于右边界，返回NULL if (left >= right) return NULL; //找出数组中最大数坐标 int maxIndex = left; int i; for (i = left + 1; i < right; i++) { if (nums[i] > nums[maxIndex]) maxIndex = i; } //开辟结点 BTNode* node = (BTNode*)malloc(sizeof(BTNode)); if (node == NULL) { printf("malloc fail"); exit(-1); } //将结点的值设为最大数组数组元素 node->val = nums[maxIndex]; node->left = NULL; node->right = NULL; //递归定义左孩子结点和右孩子结点 node->left = traversal(nums, left, maxIndex); node->right = traversal(nums, maxIndex + 1, right); return node; } //构建二叉树 BTNode* constructMaximumBinaryTree(int* nums, int numsSize) { BTNode* node= traversal(nums, 0, numsSize); Que q; QueueInit(&q);//初始化队列 if (node) QueuePush(&q, node); //队列不为空。循环继续 while (!QueueEmpty(&q)) { //获取队头元素 BTNode* front = QueueFront(&q); printf("%d ", front->val); //出队元素的左孩子入队列 if (front->left) QueuePush(&q, front->left); //出队元素的右孩子入队列 if (front->right) QueuePush(&q, front->right); QueuePop(&q); } printf("\n"); //销毁队列 QueueDestroy(&q); return traversal(nums, 0, numsSize); } int main() { //手动构建一颗二叉树 BTNode* node1 = BuyNode(1); BTNode* node2 = BuyNode(2); BTNode* node3 = BuyNode(3); BTNode* node4 = BuyNode(4); BTNode* node5 = BuyNode(5); BTNode* node6 = BuyNode(6); BTNode* node7 = BuyNode(7); BTNode* node8 = BuyNode(8); BTNode* node9 = BuyNode(9); BTNode* node10 = BuyNode(10); BTNode* node11 = BuyNode(11); BTNode* node12 = BuyNode(12); node10->left = node11; node10->right = node12; node11->left = NULL; node11->right = NULL; node12->left = NULL; node12->right = NULL; //构造数组，方便构造二叉树 int a[] = {1,2,3,25,4,5,6,7,8,9,19}; //计算大小 int nums = sizeof(a) / sizeof(a[0]); node1->left = node2; node2->left = node3; node3->left = node5; node3->right = node6; node2->right = node4; node1->right = node7; node7->left = node8; node7->right = node9; node9->left = node10; printf("翻转前（原树）：\n"); printf("前序遍历：\n"); PrevOrder(node1); printf("\n"); printf("中序遍历：\n"); InOrder(node1); printf("\n"); printf("\n"); printf("后序遍历：\n"); PostOrder(node1); printf("\n"); printf("\n"); printf("层序遍历结果为：\n"); LevelOrder(node1); printf("\n"); int ret1 = BinaryTreeSize(node1); printf("树节点的总个数: %d：\n", ret1); int ret2 = BinaryTreeLeafSize(node1); printf("叶子节点个数为: %d：\n", ret2); int ret3 = BinaryTreeKLeveSize(node1, 3); printf("第3层节点个数为: %d：\n", ret3); int ret4 = sumOfLeftLeaves(node1); printf("左叶子之和为: %d：\n", ret4); printf("\n"); printf("判断从3根节点开始是否为原树的子树：%d\n", isSubtree(node1, node3)); printf("判断是否存在满足目标值(16)的路径：%d\n", hasPathSum(node1, 16)); printf("树的高度为：%d\n", TreeHeight(node1)); printf("树最大深度为：%d\n", maxDepth(node1)); printf("树最左下角的值为：%d\n", findBottomLeftValue(node1)); printf("是否为单值二叉树：%d\n", isUnivalTree(node1)); printf("是否为完全二叉树：%d\n", TreeComplete(node1)); printf("完全二叉树的节点个数为：%d\n", countNodes(node1)); printf("是否为平衡二叉树：%d\n", isBalanced(node1)); printf("将两个二叉树合并后：\n"); mergeTrees(node1, node10); printf("\n"); printf("\n"); //翻转后： printf("翻转后：\n"); invertTree(node1); printf("\n"); printf("前序遍历：\n"); PrevOrder(node1); printf("\n"); printf("\n"); printf("中序遍历：\n"); InOrder(node1); printf("\n"); printf("\n"); printf("后序遍历：\n"); PostOrder(node1); printf("\n"); printf("\n"); printf("层序遍历结果为：\n"); LevelOrder(node1); printf("\n"); int ret5=BinaryTreeSize(node1); printf("树节点的总个数: %d：\n",ret1); int ret6=BinaryTreeLeafSize(node1); printf("叶子节点个数为: %d：\n",ret2); int ret7=BinaryTreeKLeveSize(node1, 3); printf("第3层节点个数为: %d：\n",ret3); int ret8 = sumOfLeftLeaves(node1); printf("左叶子之和为: %d：\n", ret4); printf("判断从3根节点开始是否为原树的子树：%d\n", isSubtree(node1, node3)); printf("判断是否存在满足目标值(16)的路径：%d\n", hasPathSum(node1, 16)); printf("树的高度为：%d\n", TreeHeight(node1)); printf("最大深度为：%d\n", maxDepth(node1)); printf("最小深度为：%d\n", minDepth(node1)); printf("树1最左下角的值为：%d\n",findBottomLeftValue(node1)); printf("树2最左下角的值为%d\n",findBottomLeftValue(node10)); printf("树1是否为单值二叉树：%d\n", isUnivalTree(node1)); printf("树2是否为单值二叉树：%d\n", isUnivalTree(node10)); printf("树1是否为完全二叉树：%d\n", TreeComplete(node1)); printf("树2是否为完全二叉树：%d\n", TreeComplete(node10)); printf("树1是否为平衡二叉树：%d\n", isBalanced(node1)); printf("树2是否为平衡二叉树：%d\n", isBalanced(node10)); printf("构建的最大二叉树为：\n"); constructMaximumBinaryTree(a, nums); printf("将两个二叉树合并后：\n"); mergeTrees(node1, node10); //销毁 TreeDestroy(node1); node1 = NULL; return 0; }
