超容易理解+模版套路解决LeetCode 前序+中序、中序+后序、前序+后序遍历构造树问题
这三道题的解法类似 都是基于归并排序的分治思想 不断划分左右子树进行解答。下列题1和题2解法几乎完全相同 题三根据前序后序遍历的话需要加以注意 后面详细讲解LeetCode-105. 从前序与中序遍历序列构造二叉树
题目描述
给定两个整数数组 preorder 和 inorder：
preorder是二叉树的 前序遍历 序列。inorder是同一棵树的 中序遍历 序列。
请根据这两个数组 构造 出该二叉树，并返回其根节点。
示例展示
示例 1:
输入:preorder = [3, 9, 20, 15, 7]
inorder = [9, 3, 15, 20, 7]
输出:[3, 9, 20, null, null, 15, 7]
示例 2:
输入:preorder = [-1]
inorder = [-1]
输出:[-1]
提示条件
1 <= preorder.length <= 3000inorder.length == preorder.length-3000 <= preorder[i], inorder[i] <= 3000preorder和inorder均 无重复 元素。inorder中的所有元素均出现在preorder中。preorder保证为二叉树的前序遍历序列。inorder保证为二叉树的中序遍历序列。
解题思路
根据前序遍历和中序遍历的特点可知 前序遍历是中->左->右，中序遍历是左 ->中->右，那根据两个遍历的特点 我们就可以想到：通过前序遍历来确定中间节点 然后通过中序遍历来划分左右节点 然后通过回溯把树串起来即可 多说无益 直接上代码展示
代码
/** * 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; * } * } */classSolution{//记录preorder走到哪里了int index =0;publicTreeNodebuildTree(int[] preorder,int[] inorder){returndfs(preorder,inorder,0,preorder.length-1);}publicTreeNodedfs(int[] preorder,int[] inorder,int left,int right){if(left>right){returnnull;}int mid =0;//找出用于划分左右子树的根节点for(int i = left;i<=right;i++){if(inorder[i]==preorder[index]){ mid = i;break;}}TreeNode root =newTreeNode(preorder[index]); index++;//注意顺序 先序遍历是先左节点后右边 root.left =dfs(preorder,inorder,left,mid-1); root.right =dfs(preorder,inorder,mid+1,right);return root;}}注意: 给root左右节点赋值的顺序要根据先序还是后序遍历来调整 下面第二题也就是这里做出了调整
LeetCode-106. 从中序与后序遍历序列构造二叉树
题目描述
给定两个整数数组 inorder 和 postorder：
inorder是二叉树的 中序遍历 序列。postorder是同一棵树的 后序遍历 序列。
请根据这两个数组 构造 出该二叉树，并返回其根节点。
示例展示
示例 1:
输入:inorder = [9, 3, 15, 20, 7]
postorder = [9, 15, 7, 20, 3]
示例 2:
输入:inorder = [-1]
postorder = [-1]
输出:[-1]
提示条件
1 <= inorder.length <= 3000postorder.length == inorder.length-3000 <= inorder[i], postorder[i] <= 3000inorder和postorder都由 不同 的值组成。postorder中的每一个值都在inorder中。inorder保证是树的中序遍历序列。postorder保证是树的后序遍历序列。
解题思路
这题跟上题思路完全一样 由于前序和后序遍历具有对称性 因此代码也是复用的 同样是根据后序遍历来找出中序遍历中的根节点 直接上代码
代码
/** * 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; * } * } */classSolution{//记录postorder走到哪里了int index;publicTreeNodebuildTree(int[] inorder,int[] postorder){ index = inorder.length-1;returndfs(inorder,postorder,0,inorder.length-1);}publicTreeNodedfs(int[] inorder,int[] postorder,int left,int right){if(left>right){returnnull;}int mid =0;//找出用于划分左右子树的根节点for(int i=left;i<=right;i++){if(inorder[i]==postorder[index]){ mid = i;break;}}TreeNode root =newTreeNode(postorder[index]); index--;//注意好顺序 后序遍历是先访问右节点再访问左节点 root.right =dfs(inorder,postorder,mid+1,right); root.left =dfs(inorder,postorder,left,mid-1);return root;}}以下是为您优化后的 889. 根据前序与后序遍历序列构造二叉树 的 Markdown 样式：
LeetCode-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 <= 301 <= preorder[i] <= preorder.lengthpreorder中所有值都 不同。postorder.length == preorder.length1 <= postorder[i] <= postorder.lengthpostorder中所有值都 不同。- 保证
preorder和postorder是同一棵二叉树的有效遍历序列。
解题思路
这题和前两题略有不同 前两题可以根据中序遍历来区分左右子树 但是这题并没有明确的中间节点可以用 因此不能像前两题一样到下一层递归的时候再找“接班人” 要提前去找好 不同点就在这里 其余的还是模版代码
代码
classSolution{int index =0;// 前序从 0 开始publicTreeNodeconstructFromPrePost(int[] preorder,int[] postorder){returndfs(preorder, postorder,0, postorder.length -1);}publicTreeNodedfs(int[] preorder,int[] postorder,int left,int right){if(left > right)returnnull;// 1. 取出当前前序指针指向的值作为根TreeNode root =newTreeNode(preorder[index]); index++;// 消耗当前根// 【核心特殊点 1】：叶子检查// 如果 left == right，说明当前范围就这一个数，且已经被 new 过了，// 后面已经没有“左子树根”可以找了，必须直接返回，否则 index 会越界。if(left == right)return root;// 2. 【核心特殊点 2】：找“接班人”// 此时 index 已经指向了下一个数，它是【左子树的根】// 我们去后序数组里找这个“左根”的位置 midint mid =0;for(int i = left; i <= right; i++){if(postorder[i]== preorder[index]){ mid = i;break;}}// 3. 划分边界// 左子树：从 left 到 mid（后序中左子树根是左侧部分的最后一个，所以含 mid） root.left =dfs(preorder, postorder, left, mid);// 右子树：从 mid+1 到 right-1（必须减 1 是因为要把后序数组末尾的当前根踢出去） root.right =dfs(preorder, postorder, mid +1, right -1);return root;}}以上就是这三道题的总结 有疑问的话欢迎小伙伴们提问～
