654.最大二叉树
654. 最大二叉树 - 力扣（LeetCode）
代码随想录 (programmercarl.com)
又是构造二叉树，又有很多坑！| LeetCode：654.最大二叉树_哔哩哔哩_bilibili
给定一个不重复的整数数组
nums。 最大二叉树 可以用下面的算法从nums递归地构建:
- 创建一个根节点，其值为
nums中的最大值。- 递归地在最大值 左边 的 子数组前缀上 构建左子树。
- 递归地在最大值 右边 的 子数组后缀上 构建右子树。
返回
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]提示：
1 <= nums.length <= 10000 <= nums[i] <= 1000nums中的所有整数 互不相同
这个题一开始读题没怎么读懂且有非常多的疑惑，比如最大值不在中间在两端的话怎么办？那这棵树是不是就瘸了？比如左右子树怎么构造？是不是要比较大小？
于是我就去看卡哥题解了。看了发现我没抓住重点。比如这个题的遍历方式应该为前序遍历，而且构造树的遍历方式都应该为前序遍历。这是因为构造树的时候需要先构造根节点，然后左右孩子才有着陆点。
递归三部曲：
1、确定参数和返回值：参数传入的是存放数值的元组，返回类型是指向节点的指针
class Solution{
public TreeNode constructMaximumBinaryTree(int[] nums){
return constructMaximumBinaryTree1(nums, 0, nums.length);
}
}2、确定终止条件：当递归遍历的时候，数组大小为1时，说明遍历到了叶子节点，终止遍历。
// 如果右边界索引减左边界索引等于 1，说明只有一个元素，返回包含该元素的新节点
if (rightIndex - leftIndex == 1) {
return new TreeNode(nums[leftIndex])
}3、确定单层递归的逻辑：
先找到数组中最大的值和对应的下标， 最大的值构造根节点，下标用来下一步分割数组。
public TreeNode constructMaximumBinaryTree1(int[] nums, int leftIndex, int rightIndex){
if(rightIndex - leftIndex < 1){
return null;
}
if(rightIndex - leftIndex == 1){
return new TreeNode(nums[leftIndex]);
}
int maxIndex = leftIndex;
int maxVal = nums[maxIndex];
for(int i = leftIndex + 1; i < rightIndex; i++){
if(nums[i] > maxVal) {
maxVal = nums[i];
maxIndex = i;
}
}
}最大值所在的下标左区间 构造左子树；最大值所在的下标右区间 构造右子树
TreeNode root = new TreeNode(maxVal);
// 根据maxIndex划分左右子树
root.left = constructMaximumBinaryTree1(nums, leftIndex, maxIndex);
root.right = constructMaximumBinaryTree1(nums, maxIndex + 1, rightIndex);
return root;综合代码：
class Solution {
// 构建最大二叉树的入口函数，传入整数数组 nums
public TreeNode constructMaximumBinaryTree(int[] nums) {
// 调用辅助函数 constructMaximumBinaryTree1，传入数组 nums、左边界索引 0 和右边界索引 nums.length
return constructMaximumBinaryTree1(nums, 0, nums.length);
}
// 辅助函数，用于构建最大二叉树，传入数组 nums、左边界索引 leftIndex 和右边界索引 rightIndex
public TreeNode constructMaximumBinaryTree1(int[] nums, int leftIndex, int rightIndex) {
// 如果右边界索引减左边界索引小于 1，说明没有元素了，返回 null
if (rightIndex - leftIndex < 1) {
return null;
}
// 如果右边界索引减左边界索引等于 1，说明只有一个元素，返回包含该元素的新节点
if (rightIndex - leftIndex == 1) {
return new TreeNode(nums[leftIndex]);
}
// 初始化最大值所在位置为左边界索引，最大值为对应位置的数组元素
int maxIndex = leftIndex;
int maxVal = nums[maxIndex];
// 遍历数组，找到最大值及其所在位置
for (int i = leftIndex + 1; i < rightIndex; i++) {
if (nums[i] > maxVal) {
maxVal = nums[i];
maxIndex = i;
}
}
// 创建根节点，值为最大值
TreeNode root = new TreeNode(maxVal);
// 根据最大值所在位置将数组划分为左右两部分，分别递归构建左右子树
root.left = constructMaximumBinaryTree1(nums, leftIndex, maxIndex);
root.right = constructMaximumBinaryTree1(nums, maxIndex + 1, rightIndex);
return root; // 返回根节点
}
}
617.合并二叉树
617. 合并二叉树 - 力扣（LeetCode）
代码随想录 (programmercarl.com)
一起操作两个二叉树？有点懵！| LeetCode：617.合并二叉树_哔哩哔哩_bilibili
给你两棵二叉树：
root1和root2。想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。
返回合并后的二叉树。
注意: 合并过程必须从两个树的根节点开始。
示例 1：
输入：root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7] 输出：[3,4,5,5,4,null,7]示例 2：
输入：root1 = [1], root2 = [1,2] 输出：[2,2]提示：
- 两棵树中的节点数目在范围
[0, 2000]内-104 <= Node.val <= 104
第一想法是将两个二叉树同时遍历，如果相同位置都有值则把同位置的值相加后放到新二叉树的同一位置上；如果同一位置上，有一颗二叉树没有值，则把另外一个有值的值放到新二叉树的对应位置上。但是代码实现没想法。
看了题解：
递归三部曲：
1、确定参数和返回值：参数是要传入两个二叉树的根节点，返回值就是合并之后二叉树的根节点。
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
return root1;
}2、确定终止条件：
因为是传入了两个树，那么就有两个树遍历的节点t1 和 t2，如果t1 == NULL 了，两个树合并就应该是 t2 了（如果t2也为NULL也无所谓，合并之后就是NULL）。
反过来如果t2 == NULL，那么两个数合并就是t1（如果t1也为NULL也无所谓，合并之后就是NULL）。
// 如果root1为空，返回root2，表示以root2为基准进行合并
if (root1 == null) return root2;
// 如果root2为空，返回root1，表示以root1为基准进行合并
if (root2 == null) return root1;3、确定单层递归的逻辑：
// 将root2的值加到root1的值上
root1.val += root2.val;
// 递归合并左子树，将合并结果赋给root1的左子树
root1.left = mergeTrees(root1.left, root2.left);
// 递归合并右子树，将合并结果赋给root1的右子树
root1.right = mergeTrees(root1.right, root2.right);
// 返回合并后的root1树
return root1;综合代码：
class Solution {
// 定义一个类Solution，用于解决问题
// 递归函数，合并两棵二叉树，参数为树的根节点root1和根节点root2
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
// 如果root1为空，返回root2，表示以root2为基准进行合并
if (root1 == null) return root2;
// 如果root2为空，返回root1，表示以root1为基准进行合并
if (root2 == null) return root1;
// 将root2的值加到root1的值上
root1.val += root2.val;
// 递归合并左子树，将合并结果赋给root1的左子树
root1.left = mergeTrees(root1.left, root2.left);
// 递归合并右子树，将合并结果赋给root1的右子树
root1.right = mergeTrees(root1.right, root2.right);
// 返回合并后的root1树
return root1;
}
}
