做pc网站软件,软件开发培训去哪个机构,wordpress云主机安装,wordpress特别慢#x1f680; 算法题 #x1f680; #x1f332; 算法刷题专栏 | 面试必备算法 | 面试高频算法 #x1f340; #x1f332; 越难的东西,越要努力坚持#xff0c;因为它具有很高的价值#xff0c;算法就是这样✨ #x1f332; 作者简介#xff1a;硕风和炜#xff0c;… 算法题 算法刷题专栏 | 面试必备算法 | 面试高频算法 越难的东西,越要努力坚持因为它具有很高的价值算法就是这样✨ 作者简介硕风和炜CSDN-Java领域优质创作者保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享 恭喜你发现一枚宝藏博主,赶快收入囊中吧 人生如棋我愿为卒行动虽慢可谁曾见我后退一步 算法题 目录 题目链接⛲ 题目描述 求解思路实现代码运行结果⚡ DFS 求解思路 实现代码 运行结果 共勉 题目链接
889. 根据前序和后序遍历构造二叉树
⛲ 题目描述
给定两个整数数组preorder 和 postorder 其中 preorder 是一个具有 无重复 值的二叉树的前序遍历postorder 是同一棵树的后序遍历重构并返回二叉树。
如果存在多个答案您可以返回其中 任何 一个。
示例 1
输入preorder [1,2,4,5,3,6,7], postorder [4,5,2,6,7,3,1] 输出[1,2,3,4,5,6,7] 示例 2:
输入: preorder [1], postorder [1] 输出: [1]
提示
1 preorder.length 30 1 preorder[i] preorder.length preorder 中所有值都 不同 postorder.length preorder.length 1 postorder[i] postorder.length postorder 中所有值都 不同 保证 preorder 和 postorder 是同一棵二叉树的前序遍历和后序遍历 求解思路实现代码运行结果 ⚡ DFS 求解思路
该题主要是通过前序和后序遍历来还原一颗二叉树这也就导致这棵二叉树不一定是唯一的。核心的思路先在前序遍历中找到左子树的位置preorder[1]然后在后序遍历中找到对应的下标位置对其加1得到左子树的大小这就是突破点根据左右子树分割前序和后序数组左子树的前序数组取到的区间是[1,1i)前序数组取到的区间是[1i,n)。右子树的前序数组取到的区间是[0,i)前序数组取到的区间是[i,n-1)。对其左右子树递归这个过程还原一颗二叉树。有了基本的思路接下来我们就来通过代码来实现一下递归和迭代的解法。 实现代码
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val val;* this.left left;* this.right right;* }* }*/
class Solution {public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {int n preorder.length;if (n 0) {return null;}if (n 1) {return new TreeNode(preorder[0]);}TreeNode root new TreeNode(preorder[0]);for (int i 0;; i) {if (postorder[i] preorder[1]) {i i 1;// 下标加1root.left constructFromPrePost(Arrays.copyOfRange(preorder, 1, 1 i),Arrays.copyOfRange(postorder, 0, i));root.right constructFromPrePost(Arrays.copyOfRange(preorder, 1 i, n),Arrays.copyOfRange(postorder, i, n - 1));break;}}return root;}
}运行结果 共勉
最后我想和大家分享一句一直激励我的座右铭希望可以与大家共勉
