免费字体设计 常见网站,2021年免费的网站有哪些,七牛云怎么样,网页怎么认证文章目录 LeetCode每五日一总结【01/01--01/05】2023/12/31今日数据结构#xff1a;二叉树的前/中/后 序遍历非递归 2024/01/01今日数据结构#xff1a;二叉树的 前/中/后 序遍历 三合一代码非递归今日数据结构#xff1a;二叉树的 前/中/后 序遍历 三合一代… 文章目录 LeetCode每五日一总结【01/01--01/05】2023/12/31今日数据结构二叉树的前/中/后 序遍历非递归 2024/01/01今日数据结构二叉树的 前/中/后 序遍历 三合一代码非递归今日数据结构二叉树的 前/中/后 序遍历 三合一代码递归 2024/01/02每日力扣[101. 对称二叉树](https://leetcode.cn/problems/symmetric-tree/) 2024/01/03每日力扣[104. 二叉树的最大深度](https://leetcode.cn/problems/maximum-depth-of-binary-tree/)每日力扣[111. 二叉树的最小深度](https://leetcode.cn/problems/minimum-depth-of-binary-tree/) 2024/01/04每日力扣[226. 翻转二叉树](https://leetcode.cn/problems/invert-binary-tree/) 2024/01/05每日力扣[105. 从前序与中序遍历序列构造二叉树](https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/)每日力扣[106. 从中序与后序遍历序列构造二叉树](https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/) LeetCode每五日一总结【01/01–01/05】 这次总结额外加上2023年最后一天2023/12/31日的题目总共六天 2023/12/31 二叉树的前/中/后 序遍历非递归 使用非递归方式实现二叉树的前/中/后序遍历最终要的思想是需要用到栈这样的数据结构因为我们需要在遍历的过程中时刻记着返回的路以便我们遍历完一颗子树后可以返回回来遍历其他子树 具体的前序遍历时需要在当前节点不为空时就直接操作当前节点待操作完成后再将当前节点入栈并且指向当前节点的左孩子循环该操作直到当当前节点为空则开始准备返回此时从栈中pop节点并判断pop出的节点是否有右孩子如果有则将右孩子赋值给当前节点继续上面的操作即可。 中序遍历的代码思想和前序遍历是非常类似的只是在操作节点的时机上有所不同前序遍历是在当节点不为空时直接操作节点而中序遍历则需要在当前节点为空后从栈中pop出第一个元素时操作pop出的元素因为此时pop出的元素已经没有左孩子。 后序遍历的代码和前序遍历及中序遍历有所区别最大的区别在于当当前节点为空时我们不能立刻从栈顶pop节点并操作该节点而应该先判断栈顶元素节点的右孩子没有或者已经被操作那么判断栈顶节点右孩子为空很容易如何判断栈顶节点右孩子是否被操作过呢此时我们可以定义一个变量pop记录最近一次被pop出的节点如果栈顶元素的右孩子和记录的pop变量中的节点是同一个节点则说明栈顶元素的右孩子以及被操作此时即可pop出栈顶节点进行操作。如果不是同一个节点则将说明栈顶元素有右孩子而且暂时没有被操作此时要将右孩子赋值给当前节点重复以上判断。 2024/01/01 二叉树的 前/中/后 序遍历 三合一代码非递归 所谓三合一代码就是将之前分开写的三段递归代码合在一段代码中在代码的不同时机进行不同的节点操作即可实现一段代码进行了前/中/后三次遍历的效果有助于进一步理解二叉树的三种遍历方式不同点在于操作栈中的节点大家可以重点关注 二叉树的 前/中/后 序遍历 三合一代码递归 递归实现二叉树的遍历代码很简单易懂附上代码不过多赘述 2024/01/02 101. 对称二叉树 这道题判断一个二叉树是否是对称的我们可以想到判断根节点的左右孩子是否是对称的其他节点的判断方法和根节点相同很容易想到采用递归方法因此在check方法中定义好判断条件 如果left和right都为空返回true因为它们都是空的。如果left或right为空返回false因为其中一个树不是空的。如果left和right的值不相等返回false因为树不是对称的。 后只需递归左孩子的左孩子和右孩子的右孩子为参数调用该方法即可判断整颗树是否为对称树 2024/01/03 104. 二叉树的最大深度 方法一后序遍历递归法 判断根节点是否为空如果是则返回0因为深度为0。如果根节点的左右子节点都为空说明该节点没有子节点返回1因为深度为1。否则递归地计算左子树和右子树的深度分别存储在maxLeft和maxRight变量中。最后将maxLeft和maxRight中的最大值加1得到本节点的最大深度并返回。 关于深度的定义从根节点出发离根节点最远的节点所经过的边数即该节点的深度。注意这里的深度定义与力扣上的默认定义略有不同深度为0表示没有节点深度为1表示有一个根节点深度为2表示有一个根节点和一个子节点以此类推。 方法二后序遍历非递归法 非递归法实现二叉树的后序遍历时需要使用到栈数据结构用于记录遍历一颗子树完成后返回的路此时如果是后序遍历只有遍历到叶子节点时才会从栈中pop元素因此栈中最大的元素个数就对应着二叉树的最大深度我们只需要在向栈中放入元素方法后面记录栈中元素个数返回最大的元素个数即可。 方法三层序遍历 使用层序遍历计算二叉树的最大深度我们只需要定义一个记录深度的变量在遍历完每一层的所有节点后该变量1即可。 111. 二叉树的最小深度 方法一二叉树的最小深度递归 思路当根节点没有左右孩子则返回最小深度为1当根节点只有左孩子则递归调用求出左孩子的最小深度1即可相同的如果根节点只有右孩子则递归调用求出右孩子的最小深度1即可 对于一个非空节点如果它的左子节点和右子节点都为空那么它的最小深度为1****如果它的左子节点为空那么它的最小深度为右子节点的最小深度加1如果它的右子节点为空那么它的最小深度为左子节点的最小深度加1****否则它的最小深度为左右子节点最小深度的较小值加1。 如果根节点为空则返回0。如果根节点的左子节点和右子节点都为空则返回1。如果根节点的左子节点为空则返回根节点的右子节点的最小深度加1。如果根节点的右子节点为空则返回根节点的左子节点的最小深度加1。否则返回左右子节点最小深度的较小值加1。 方法二二叉树的最小深度层序遍历❤️效率更优 核心思想当层序遍历找到第一个叶子节点时返回第一个叶子节点所在层数即为最小深度。 #注意应当在循环遍历每一层节点之前先将层数1此时的层数变量才表示当前层 2024/01/04 226. 翻转二叉树 主要逻辑 如果当前节点为空则返回因为不需要对空节点进行反转。定义一个节点对象 t用于充当中间过渡节点先将左子树赋值给中间节点。将右子树赋值给左子树节点。将中间节点中存放的左子树赋值给右子树完成根节点的左右子树反转。递归调用 fn 方法将根节点的左孩子的孩子节点反转。将根节点的右孩子的孩子节点反转。 2024/01/05 105. 从前序与中序遍历序列构造二叉树 主要逻辑 如果输入的数组为空则返回空。取前序遍历数组的第一个元素作为根节点的值。遍历中序遍历数组找到根节点所在位置。根据根节点的位置将中序遍历数组分为左部分和右部分其中左部分即为根节点左子树的中序遍历数组右部分即为根节点右子树的中序遍历数组。根据左部分和中序遍历数组左部分的个数将前序遍历数组从第二个元素开始分为左部分和右部分其中左部分即为根节点左子树的前序遍历数组右部分即为根节点右子树的前序遍历数组。分别递归地构造根节点的左子树和右子树并将它们分别作为根节点的左子树节点和右子树节点。返回根节点。 106. 从中序与后序遍历序列构造二叉树 主要逻辑 如果输入的数组为空则返回空。取后序遍历数组的最后一个元素作为根节点的值。遍历中序遍历数组找到根节点所在位置。根据根节点的位置将中序遍历数组分为左部分和右部分其中左部分即为根节点左子树的中序遍历数组右部分即为根节点右子树的中序遍历数组。根据左部分和中序遍历数组左部分的个数将后序遍历数组从第一个元素开始分为左部分和右部分其中左部分即为根节点左子树的后序遍历数组右部分即为根节点右子树的后序遍历数组。分别递归地构造根节点的左子树和右子树并将它们分别作为根节点的左子树节点和右子树节点。返回根节点。 2023/12/31
今日数据结构二叉树的前/中/后 序遍历非递归
前序遍历 中序遍历 后序遍历 2024/01/01
今日数据结构二叉树的 前/中/后 序遍历 三合一代码非递归 今日数据结构二叉树的 前/中/后 序遍历 三合一代码递归 2024/01/02
每日力扣101. 对称二叉树 给你一个二叉树的根节点 root 检查它是否轴对称。 示例 1 输入root [1,2,2,3,4,4,3]
输出true示例 2 输入root [1,2,2,null,3,null,3]
输出false提示 树中节点数目在范围 [1, 1000] 内-100 Node.val 100 **进阶**你可以运用递归和迭代两种方法解决这个问题吗 public boolean isSymmetric(TreeNode root) {return check(root.left, root.right);}private boolean check(TreeNode left, TreeNode right) {if (left null right null) {return true;}if (left null || right null) {return false;}if (left.val ! right.val) {return false;}return check(left.left, right.right) check(left.right, right.left);}这段Java代码定义了一个名为isSymmetric的方法该方法接受一个TreeNode对象作为输入并返回一个布尔值。该方法检查以root为根的树是否对称。 check是一个私有辅助方法它接受两个TreeNode对象作为输入并返回一个布尔值。它通过比较两个树的根值并递归地检查它们的左和右子树是否对称来检查两个树是否对称。 isSymmetric方法的逻辑如下 如果left和right都为空返回true因为它们都是空的。如果left或right为空返回false因为其中一个树不是空的。如果left和right的值不相等返回false因为树不是对称的。如果left和right的值相等调用check方法对left和right的左和右子树进行递归比较并返回结果。 isSymmetric方法返回true如果树是对称的否则返回false。 2024/01/03
每日力扣104. 二叉树的最大深度 给定一个二叉树 root 返回其最大深度。 二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。 示例 1 输入root [3,9,20,null,null,15,7]
输出3示例 2 输入root [1,null,2]
输出2提示 树中节点的数量在 [0, 104] 区间内。-100 Node.val 100 /*** 求树的最大深度后序遍历-递归*/
public class Leetcode104_1 {/*思路1. 得到左子树深度, 得到右子树深度, 二者最大者加一, 就是本节点深度2. 因为需要先得到左右子树深度, 很显然是后序遍历典型应用3. 关于深度的定义从根出发, 离根最远的节点总边数,注意: 力扣里的深度定义要多一深度2 深度3 深度11 1 1/ \ / \2 3 2 3\4*/public int maxDepth(TreeNode root) {if (root null) {return 0;}if (root.left null root.right null) {return 1;}//得到左子树深度int maxLeft maxDepth(root.left);//得到右子树深度int maxRight maxDepth(root.right);//二者最大者加一, 就是本节点深度return Integer.max(maxLeft, maxRight) 1;}
}方法一求树的最大深度**后序遍历-递归** ❤️ 利用递归方法逻辑是 得到左子树深度, 得到右子树深度, 二者最大者加一, 就是本节点深度因为需要先得到左右子树深度, 很显然是后序遍历典型应用 要求先操作左右子树的题目可以想到后序遍历。 这段Java代码是Leetcode上的第104题的解法。题目要求给定一个二叉树返回其最大深度。 首先定义了一个名为Leetcode104_1的类其中包含一个名为maxDepth的方法该方法接受一个Tree Node类型的参数表示二叉树的根节点。 maxDepth方法的主要思路如下 判断根节点是否为空如果是则返回0因为深度为0。如果根节点的左右子节点都为空说明该节点没有子节点返回1因为深度为1。否则递归地计算左子树和右子树的深度分别存储在maxLeft和maxRight变量中。最后将maxLeft和maxRight中的最大值加1得到本节点的最大深度并返回。 关于深度的定义**从根节点出发离根节点最远的节点所经过的边数即该节点的深度。**注意这里的深度定义与力扣上的默认定义略有不同深度为0表示没有节点深度为1表示有一个根节点深度为2表示有一个根节点和一个子节点以此类推。 总之这段代码的主要目的是通过递归地计算左右子树的深度然后找到它们中的最大值最后将该最大值加1得到本节点的最大深度。 /*** 求二叉树的最大深度后序遍历-非递归*/
public class Leetcode104_2 {public int maxDepth(TreeNode root) {TreeNode curr root;//非递归方法遍历树需要栈数据结构LinkedListTreeNode stack new LinkedList();//非递归法实现后序遍历需要定义一个指针记录最近一次从栈中弹出的元素TreeNode pop null;//记录最大深度int max 0;while (curr ! null || !stack.isEmpty()) {if (curr ! null) {stack.push(curr);//在向栈中添加元素后栈中元素个数发生改变栈中最大元素个数就是树的最大深度int size stack.size();if (size max) {max size;}curr curr.left;} else {TreeNode peek stack.peek();if (peek.right null || peek.right pop) {pop stack.pop();} else {curr peek.right;}}}return max;}
}方法二 求二叉树的最大深度**后序遍历-非递归** 这段Java代码是Leetcode上的第104题的另一个解法。题目要求给定一个二叉树返回其最大深度。 与上一个解法不同这个解法使用了非递归的方法遍历二叉树。在遍历过程中使用一个栈来存储当前节点及其路径上的节点同时记录栈中的最大元素个数即为二叉树的最大深度。 具体实现如下 初始化一个栈一个用于记录最大深度的变量max以及一个用于记录最近一次出栈节点的变量pop。如果当前节点不为空则将当前节点入栈并将栈中元素个数与当前最大深度进行比较如果栈中元素个数大于当前最大深度则更新最大深度。如果当前节点为空则将栈顶节点出栈如果栈顶节点的右子节点为空或者右子节点已经被访问过即与pop相等则将栈顶节点出栈否则将右子节点入栈。重复步骤2和3直到栈为空。返回最大深度。 这个解法的时间复杂度为O(n)空间复杂度为O(n)其中n为二叉树的节点个数。 /*** 二叉树的最大深度层序遍历*/
SuppressWarnings(all)
public class Leetcode104_3 {public int maxDepth(TreeNode root) {if (root null) {return 0;}//二叉树的层序遍历需要用到队列数据结构QueueTreeNode queue new LinkedList();queue.offer(root);//记录深度int depth 0;while (!queue.isEmpty()) {//每一层节点个数队列中元素个数记录的就是每一层节点的个数int size queue.size();//当前层有多少节点就循环多少次for (int i 0; i size; i) {//就把多少节点从队列中弹出并把它们的孩子加入队列TreeNode pollNode queue.poll();if (pollNode.left ! null) {queue.offer(pollNode.left);}if (pollNode.right ! null) {queue.offer(pollNode.right);}}//每循环一层层数 1depth;}//当循环完所有节点返回层数return depth;}
}方法三二叉树的最大深度**层序遍历** 与上一个解法不同这个解法使用了二叉树的层序遍历方法。在遍历过程中记录每一层的节点个数当遍历完一层后将深度加1直到队列为空此时的深度即为二叉树的最大深度。 具体实现如下 如果根节点为空则返回0。初始化一个队列用于存储二叉树的节点并将根节点入队。初始化一个深度变量depth用于记录二叉树的层数。当队列不为空时进入循环 a. 计算队列中的节点个数size用于表示当前层的节点个数。 b. 循环size次表示当前层有size个节点 i. 从队列中弹出一个节点pollNode。 ii. 如果pollNode的左子节点不为空则将左子节点入队。 iii. 如果pollNode的右子节点不为空则将右子节点入队。 c. 每循环一次表示当前层遍历完毕将深度加1。当队列为空时跳出循环返回深度变量depth。 这个解法的时间复杂度为O(n)空间复杂度为O(n)其中n为二叉树的节点个数。 每日力扣111. 二叉树的最小深度 给定一个二叉树找出其最小深度。 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 **说明**叶子节点是指没有子节点的节点。 示例 1 输入root [3,9,20,null,null,15,7]
输出2示例 2 输入root [2,null,3,null,4,null,5,null,6]
输出5提示 树中节点数的范围在 [0, 105] 内-1000 Node.val 1000 /*** 二叉树的最小深度b递归/b*/
public class Leetcode111_1 {public int minDepth(TreeNode root) {if (root null) {return 0;}int minLeft minDepth(root.left);int minRight minDepth(root.right);if (minRight 0) {return minLeft 1;}if (minLeft 0) {return minRight 1;}return Integer.min(minLeft, minRight) 1;}
}方法一二叉树的最小深度**递归** 这段Java代码是Leetcode上的第111题的另一个解法。题目要求给定一个二叉树返回其最小深度。 与上一个解法不同这个解法使用了递归的方法。对于一个非空节点如果它的左子节点和右子节点都为空那么它的最小深度为1****如果它的左子节点为空那么它的最小深度为右子节点的最小深度加1如果它的右子节点为空那么它的最小深度为左子节点的最小深度加1****否则它的最小深度为左右子节点最小深度的较小值加1。 具体实现如下 如果根节点为空则返回0。如果根节点的左子节点和右子节点都为空则返回1。如果根节点的左子节点为空则返回根节点的右子节点的最小深度加1。如果根节点的右子节点为空则返回根节点的左子节点的最小深度加1。否则返回左右子节点最小深度的较小值加1。 这个解法的时间复杂度为O(n)空间复杂度为O(n)其中n为二叉树的节点个数。 /*** 二叉树的最小深度b层序遍历/b*/
SuppressWarnings(all)
public class Leetcode111_2 {public int minDepth(TreeNode root) {if(rootnull){return 0;}//思想使用层序遍历当遍历到第一个叶子节点他所在的层就是最小深度QueueTreeNode queue new LinkedList();queue.offer(root);int Depth 0;while (!queue.isEmpty()) {Depth;int size queue.size();for (int i 0; i size; i) {TreeNode poll queue.poll();//判断是否是叶子节点if(poll.rightnullpoll.leftnull){//如果是则直接返回当前节点的层数即为深度return Depth;}if (poll.left ! null) {queue.offer(poll.left);}if (poll.right ! null) {queue.offer(poll.right);}}}return Depth;}
}方法二二叉树的最小深度****层序遍历****❤️ 核心思想 使用层序遍历当遍历到第一个叶子节点他所在的层就是最小深度 这段代码是用于计算二叉树的最小深度。它使用了一种叫做层序遍历的方法来解决这个问题。 首先如果根节点为空那么深度为0。 然后创建一个队列来存储每一层的节点。将根节点加入队列中并将深度设为1。 接下来进入一个while循环只要队列不为空就执行以下操作 将当前深度加1。计算队列的大小表示当前层的节点数量。遍历当前层的节点将它们从队列中移出并判断它们是否是叶子节点即没有左右子节点。如果找到第一个叶子节点直接返回当前节点的深度即为最小深度。如果当前节点的左右子节点都不为空将它们加入队列中。 当while循环结束时说明所有节点都已经遍历过了但仍然没有找到叶子节点那么二叉树的最小深度就是最后那层的深度。 2024/01/04
每日力扣226. 翻转二叉树 给你一棵二叉树的根节点 root 翻转这棵二叉树并返回其根节点。 示例 1 输入root [4,2,7,1,3,6,9]
输出[4,7,2,9,6,3,1]示例 2 输入root [2,1,3]
输出[2,3,1]示例 3 输入root []
输出[]提示 树中节点数目范围在 [0, 100] 内-100 Node.val 100 /*** 反转二叉树*/
public class Leetcode226 {public TreeNode invertTree(TreeNode root) {//反转方法fn(root);return root;}private void fn(TreeNode node) {//结束递归条件如果节点为空返回if (node null) {return;}//定义一个节点对象用于充当中间过渡节点先将左子树赋值给中间节点TreeNode t node.left;//将右子树赋值给左子树节点node.left node.right;//再将中间节点中存放的左子树赋值给右子树完成根节点的左右子树反转node.right t;//递归调用反转方法将根节点的左孩子的孩子节点反转fn(node.left);//将根节点的右孩子的孩子节点反转fn(node.right);}
}这段代码定义了一个名为 Leetcode226 的类它包含一个名为 invertTree 的方法该方法接受一个二叉树的根节点作为参数并返回反转后的二叉树的根节点。 该方法首先调用一个名为 fn 的私有方法该方法用于递归地反转二叉树的左右子树。 fn 方法的主要逻辑如下 如果当前节点为空则返回因为不需要对空节点进行反转。定义一个节点对象 t用于充当中间过渡节点先将左子树赋值给中间节点。将右子树赋值给左子树节点。将中间节点中存放的左子树赋值给右子树完成根节点的左右子树反转。递归调用 fn 方法将根节点的左孩子的孩子节点反转。将根节点的右孩子的孩子节点反转。 最后invertTree 方法将反转后的二叉树的根节点返回。 2024/01/05
每日力扣105. 从前序与中序遍历序列构造二叉树 给定两个整数数组 inorder 和 postorder 其中 inorder 是二叉树的中序遍历 postorder 是同一棵树的后序遍历请你构造并返回这颗 二叉树 。 示例 1: 输入inorder [9,3,15,20,7], postorder [9,15,7,20,3]
输出[3,9,20,null,null,15,7]示例 2: 输入inorder [-1], postorder [-1]
输出[-1]提示: 1 inorder.length 3000postorder.length inorder.length-3000 inorder[i], postorder[i] 3000inorder 和 postorder 都由 不同 的值组成postorder 中每一个值都在 inorder 中inorder 保证是树的中序遍历postorder 保证是树的后序遍历 public class Leetcode105 {public TreeNode buildTree(int[] preorder, int[] inorder) {/*输入: preorder [3,9,20,15,7], inorder [9,3,15,20,7]输出: [3,9,20,null,null,15,7]*///结束递归的条件当遍历数组为空时说明已经没有值返回空if (preorder.length 0) {return null;}// 前序遍历的第一个值一定是根节点的值int rootValue preorder[0];//创建根节点TreeNode root new TreeNode(rootValue);//遍历中序数组for (int i 0; i inorder.length; i) {//在中序数组中要找根节点所在位置if (inorder[i] rootValue) {//以根节点为中心将中序数组分为左部分和右部分其中左部分即为根节点左子树的中序遍历数组int[] inLeft Arrays.copyOfRange(inorder, 0, i);//右部分即为根节点右子树的中序遍历数组int[] inRight Arrays.copyOfRange(inorder, i 1, inorder.length);//通过中序遍历数组左右部分的个数右可以将前序数组从第二个值开始分为左部分和右部分int[] preLeft Arrays.copyOfRange(preorder, 1, i 1);int[] preRight Arrays.copyOfRange(preorder, i 1, inorder.length);//分别把前序数组左部分和中序数组左部分以及前序数组右部分和中序数组右部分看做一 颗数的前序遍历和中序遍历//递归调用buildTree方法返回根节点作为上一次返回根的左子树节点以及右子树节点root.left buildTree(preLeft, inLeft);root.right buildTree(preRight, inRight);// ** 切记 在中序遍历数组中找到根的值后要跳出循环break;}}//返回根节点return root;}
}这段代码定义了一个名为 Leetcode105 的类它包含一个名为 buildTree 的方法该方法接受两个整数数组 preorder 和 inorder 作为参数并返回根据这两个数组构造出的二叉树的根节点。 buildTree 方法的主要逻辑如下 如果输入的数组为空则返回空。取前序遍历数组的第一个元素作为根节点的值。遍历中序遍历数组找到根节点所在位置。根据根节点的位置将中序遍历数组分为左部分和右部分其中左部分即为根节点左子树的中序遍历数组右部分即为根节点右子树的中序遍历数组。根据左部分和中序遍历数组左部分的个数将前序遍历数组从第二个元素开始分为左部分和右部分其中左部分即为根节点左子树的前序遍历数组右部分即为根节点右子树的前序遍历数组。分别递归地构造根节点的左子树和右子树并将它们分别作为根节点的左子树节点和右子树节点。返回根节点。 在上述过程中递归地调用 buildTree 方法最终返回的根节点即为根据输入的前序遍历数组和中序遍历数组构造出的二叉树的根节点。 每日力扣106. 从中序与后序遍历序列构造二叉树 给定两个整数数组 inorder 和 postorder 其中 inorder 是二叉树的中序遍历 postorder 是同一棵树的后序遍历请你构造并返回这颗 二叉树 。 示例 1: 输入inorder [9,3,15,20,7], postorder [9,15,7,20,3]
输出[3,9,20,null,null,15,7]示例 2: 输入inorder [-1], postorder [-1]
输出[-1]提示: 1 inorder.length 3000postorder.length inorder.length-3000 inorder[i], postorder[i] 3000inorder 和 postorder 都由 不同 的值组成postorder 中每一个值都在 inorder 中inorder 保证是树的中序遍历postorder 保证是树的后序遍历 public class E10Leetcode106 {public TreeNode buildTree(int[] inorder, int[] postorder) {/*输入inorder [9,3,15,20,7], postorder [9,15,7,20,3]输出[3,9,20,null,null,15,7]*///递归结束条件if(inorder.length0){return null;}//后序遍历数组的最后一个值一定是根节点的值int rootValue postorder[postorder.length-1];//有了根节点的值创建根节点TreeNode root new TreeNode(rootValue);//拿根节点在值去中序遍历数组中找根节点的位置for (int i 0; i inorder.length; i) {//在中序遍历数组中找到根节点位置if(inorder[i] rootValue){//根据根节点位置划分数组int[] inLeft Arrays.copyOfRange(inorder,0,i);int[] inRight Arrays.copyOfRange(inorder,i1,inorder.length);//划分后序遍历数组int[] postLeft Arrays.copyOfRange(postorder,0,i);int[] postRight Arrays.copyOfRange(postorder,i,postorder.length-1);//分别把后序数组左部分和中序数组左部分以及后序数组右部分和中序数组右部分看做一 颗数的后序遍历和中序遍历//递归调用buildTree方法返回根节点作为上一次返回根的左子树节点以及右子树节点root.left buildTree(inLeft,postLeft);root.right buildTree(inRight,postRight);// ** 切记 在中序遍历数组中找到根的值后要跳出循环break;}}return root;}
}这段代码定义了一个名为 Leetcode106 的类它包含一个名为 buildTree 的方法该方法接受两个整数数组 inorder 和 postorder 作为参数并返回根据这两个数组构造出的二叉树的根节点。 buildTree 方法的主要逻辑如下 如果输入的数组为空则返回空。取后序遍历数组的最后一个元素作为根节点的值。遍历中序遍历数组找到根节点所在位置。根据根节点的位置将中序遍历数组分为左部分和右部分其中左部分即为根节点左子树的中序遍历数组右部分即为根节点右子树的中序遍历数组。根据左部分和中序遍历数组左部分的个数将后序遍历数组从第一个元素开始分为左部分和右部分其中左部分即为根节点左子树的后序遍历数组右部分即为根节点右子树的后序遍历数组。分别递归地构造根节点的左子树和右子树并将它们分别作为根节点的左子树节点和右子树节点。返回根节点。 在上述过程中递归地调用 buildTree 方法最终返回的根节点即为根据输入的中序遍历数组和后序遍历数组构造出的二叉树的根节点。
