静态网站添加到织梦,wordpress图片预加载,做暧暧暖网站欧美,网站改版被降权105#xff1a;从前序与中序遍历序列构造二叉树
啊#xff0c;好久都没有更新算法题目了。曾今是C#xff0c;如今是Java#xff0c;感慨啊。
像树这样的算法题#xff0c;基本都逃不开递归。递归的思想是#xff1a;将大任务拆分为小任务。我们不妨构建一个函数#…105从前序与中序遍历序列构造二叉树
啊好久都没有更新算法题目了。曾今是C如今是Java感慨啊。
像树这样的算法题基本都逃不开递归。递归的思想是将大任务拆分为小任务。我们不妨构建一个函数取名func1()它实现的功能是:在指定区间内, 找到并构建root节点并返回。
如果我们想要构建一棵树只需要调用func1()就能够得到树的根节点那么树的构建过程就可以简化为如下形式:
TreeNode root new TreeNode();
root.value value;
root.left func1(...);
root.right func1(...)通过func1我们即可计算得到左右节点具体的逻辑都一样
现在让我们将视角聚焦于如何构建func1()。函数内容的核心是构建root节点。构建分为三步: 1.得到root.val构建root.left构建root.right。为了解决这个内容我们先将 前序遍历中序遍历写为以下形式 前序 【root左子树右子树】 中序 【左子树root右子树】 如果我们想要确定root节点我们只需要在前序数组中获取第一个元素即可。如果我们想要确定左子树长度右子树长度我们只需要知道中序中root节点的index即可
我们假设前序数组的区间范围是 [ l 1 , r 1 ] [ l1, r1 ] [l1,r1]中序是 [ l 2 , r 2 ] [l2, r2] [l2,r2]。root节点在中序的下标是 r o o t I d x I n rootIdxIn rootIdxIn那么左子树长度 l e f L e n r o o t I n d I n − l 2 lefLen rootIndIn - l2 lefLenrootIndIn−l2右子树长度 r i g L e n r 2 − r o o t I n d I n rigLen r2 - rootIndIn rigLenr2−rootIndIn
rootValue很好获取前序[l1]。 root.left的获取我们可以交给递归函数完成。因为root.left其本质是左子树的root节点规定func1的计算范围是root节点的左子树范围即可完成计算 root.right同理。 tip : 笔者习惯将递归函数命名为dfs但这不是真正的dfs /*** 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 HashMapInteger, Integer map new HashMap();public TreeNode buildTree(int[] preorder, int[] inorder) {int n preorder.length;// 通过map映射 值-index的方式, 加速root节点在中序数组下标的定位速度for (int i 0; i inorder.length; i) {map.put(inorder[i], i);}return dfs(preorder, inorder, 0, n - 1, 0, n - 1);}public TreeNode dfs(int[] preorder, int[] inorder, int l1, int r1, int l2, int r2) {// 递归终止条件, 如果l1 r1, 表明当区间不存在, 节点值应该赋为nullif (l1 r1 || l2 r2) return null;// debugSystem.out.println(l1 l1 r1 r1 l2 l2 r2 r2);// 确定根节点int rootVal preorder[l1];// 根节点再inorder中的indexint rootIdxIn map.get(rootVal);System.out.println(rootIdxIn rootIdxIn);// 左区间长度int lefLen rootIdxIn - l2;// 右区间长度int rigLen r2 - rootIdxIn;TreeNode root new TreeNode();root.val rootVal;root.left dfs(preorder, inorder, l1 1, l1 lefLen, l2, rootIdxIn - 1);root.right dfs(preorder, inorder, l1 lefLen 1, r1, rootIdxIn 1, r2);return root;}
}
