【C++算法】最大二叉树，合并二叉树题目详细解读！
▎合并二叉树
一、题目描述
给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为NULL 的节点将直接作为新二叉树的节点。
二、示例 1:
输入:
Tree 1 Tree 2 1 2 / \ / \ 3 2 1 3 / \ \ 5 4 7
输出:
合并后的树:
3 / \ 4 5 / \ \ 5 4 7
注意: 合并必须从两个树的根节点开始。
三、递归法
前序遍历 -- 递归法
1、递归函数的参数与返回值
? 参数：两个树的节点
? 返回值：新树的节点
2、递归终止条件
? 两个树的节点一个为空一个不为空，返回不为空的节点
? 两个树的节点都为空，返回空
? 两个树的节点都不为空，返回新节点
3、单层遍历的逻辑
? 根节点
? 左节点
? 右节点
四、代码
合并后的树使用新的空间
// 递归法 class Solution { public: TreeNode *mergeTrees(TreeNode *root1, TreeNode *root2) { return traversal(root1, root2); } private: TreeNode *traversal(TreeNode *root1, TreeNode *root2) { // 判断是否有节点为空 // 返回不为空的节点 // 全为空的时候返回NULL if (root1 == NULL && root2 != NULL) { return root2; } else if (root1 != NULL && root2 == NULL) { return root1; } else if (root1 == NULL && root2 == NULL) { return NULL; } // 全都非空 // 定义新的节点，节点值为两个节点值的和 TreeNode *node = new TreeNode(root1->val + root2->val); // 左 node->left = traversal(root1->left, root2->left); // 右 node->right = traversal(root1->right, root2->right); return node; } };
原地合并
class Solution{ public: TreeNode *mergeTrees(TreeNode *root1,TreeNode *root2){ // 如果第一棵树节点为空，则返回第二棵树的节点 if(root1 ==NULL){ return root2; } if(root2 == NULL){ return root1; } // 在第一棵树上进行原地修改 // 中 root1->val += root2->val; // 左 root1->left = mergeTrees(root1->left,root2->left); // 右 root1->right = mergeTrees(root1->right,root2->right); return root1; } };
===========================================
▎最大二叉树
一、题目描述
给定一个不含重复元素的整数数组nums。一个以此数组直接递归构建的最大二叉树定义如下：
1、二叉树的根是数组nums中的最大元素。
2、左子树是通过数组中最大值左边部分递归构造出的最大二叉树。
3、右子树是通过数组中最大值右边部分递归构造出的最大二叉树。
返回有给定数组 nums 构建的最大二叉树。
二、示例 1：
输入： nums = [3,2,1,6,0,5]
输出： [6,3,5,null,2,0,null,null,1]
解释： 递归调用如下所示：
- [3,2,1,6,0,5] 中的最大值是 6 ，左边部分是 [3,2,1] ，右边部分是 [0,5] 。
- [3,2,1] 中的最大值是 3 ，左边部分是 [] ，右边部分是 [2,1] 。
- 空数组，无子节点。
- [2,1] 中的最大值是 2 ，左边部分是 [] ，右边部分是 [1] 。
- 空数组，无子节点。
- 只有一个元素，所以子节点是一个值为 1 的节点。
- [0,5] 中的最大值是 5 ，左边部分是 [0] ，右边部分是 [] 。
- 只有一个元素，所以子节点是一个值为 0 的节点。
- 空数组，无子节点。
三、示例 2：
输入： nums = [3,2,1]
输出： [3,null,2,null,1]
四、解析
类似于上一题（13、从中序与后序遍历序列构造二叉树（106））
1、如果数组为空，则返回空
2、找到数组中的最大数，作为根节点
3、将剩余的数组分为左数组和右数组
4、递归构造二叉树(处理左数组和右数组)
五、代码
class Solution { public: TreeNode *constructMaximumBinaryTree(vector<int> &nums) { return traversal(nums); } TreeNode *traversal(vector<int> &nums) { // 判断如果数组为空，则返回NULL if (nums.size() == 0) { return NULL; } // 2、查找最大值所在的位置,构造根节点 int maxIndex = 0, maxVal = MIN_INT; for (int i = 0; i < nums.size(); i++) { if (nums[i] > maxVal) { maxVal = nums[i]; maxIndex = i; } } TreeNode *root = new TreeNode(maxVal); // 3、根据根节点的所在位置，将数组分为左右数组 vector<int> leftSub(nums.begin(), nums.begin() + maxIndex); vector<int> rightSub(nums.begin() + maxIndex + 1, nums.end()); // 4、递归处理左右数组 root->left = traversal(leftSub); root->right = traversal(rightSub); return root; } };
==========================
以上就是今天的内容，希望能够对大家有所帮助！
—— C/C++编程学习入坑群 ——