2025-2-21leetcode刷题情况（二叉树的修改与构造）

一、106.从中序与后序遍历序列构造二叉树 1.题目描述

给定两个整数数组 inorder和postorder，其中 inorder 是二又树的中序遍历，postorder 是同一棵树的后序遍历，请你构造并返回这颗二又树。

2.代码

3.思路

以后序数组的最后一个元素为切割点，先切中序数组，根据中序数组，反过来再切后序数组。一层一层切下去，每次后序数组最后一个元素就是节点元素。

代码框架

二、654.最大二叉树 1.题目描述

给定一个不重复的整数数组 nums。最大二叉树 可以用下面的算法从 nums 递归地构建： 1.创建一个根节点，其值为 nums 中的最大值。 2.递归地在最大值 左边 的 子数组前缀上 构建左子树。 3.递归地在最大值 右边 的 子数组后缀上 构建右子树。 返回nums 构建的最大二叉树

2.代码

3.思路

构造树一般采用的是前序遍历，因为先构造中间节点，然后递归构造左子树和右子树。

确定递归函数的参数和返回值

参数传入的是存放元素的数组，返回该数组构造的二叉树的头结点，返回类型是指向节点的指针。

确定终止条件

题目中说了输入的数组大小一定是大于等于1的，所以我们不用考虑小于1的情况，那么当递归遍历的时候，如果传入的数组大小为1，说明遍历到了叶子节点了。

那么应该定义一个新的节点，并把这个数组的数值赋给新的节点，然后返回这个节点。 这表示一个数组大小是1的时候，构造了一个新的节点，并返回。

确定单层递归的逻辑

这里有三步工作

先要找到数组中最大的值和对应的下标， 最大的值构造根节点，下标用来下一步分割数组。最大值所在的下标左区间 构造左子树。这里要判断maxValueIndex > 0，因为要保证左区间至少有一个数值。最大值所在的下标右区间 构造右子树。判断maxValueIndex < (nums.size() - 1)，确保右区间至少有一个数值。 三、617.合并二叉树 1.题目描述

给你两棵二叉树:root1和root2 想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重(而另一些不会)。你需要将这两棵树合并成一棵新二叉树。合并的规则是:如果两个节点重，那么将这两个节点的值相加作为合并后节点的新值;否则，不为 nul的节点将直接作为新二又树的节点。 返回合并后的二叉树。 注意:合并过程必须从两个树的根节点开始。

2.代码

3.思路

这里运用的是递归方法，和遍历一棵二叉树一样，同时遍历两棵二叉树。