企业信用信息公示系统湖南_seo排名优化公司_在哪个网站可以免费做广告_百度电话怎么转人工客服

Problem: 106. 从中序与后序遍历序列构造二叉树

👨‍🏫 参考题解

🍻 Code 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 buildTree(int[] inorder, int[] postorder) {int n = postorder.length;if(n == 0){return null;}int leftSize = indexOf(inorder, postorder[n-1]);// 左区间的长度int[] in1 = Arrays.copyOfRange(inorder, 0, leftSize);int[] in2 = Arrays.copyOfRange(inorder, leftSize+1, n);// 记得排除中间的根节点int[] post1 = Arrays.copyOfRange(postorder, 0, leftSize);int[] post2 = Arrays.copyOfRange(postorder, leftSize, n-1);// 排除最后一个根节点TreeNode left = buildTree(in1, post1);TreeNode right = buildTree(in2,post2);return new TreeNode(postorder[n-1],left,right);}// 返回 x 在 a 中的下标，保证 x 一定在 a 中private int indexOf(int[] a , int x){for(int i = 0; ; i++){if(a[i] == x){return i;}}}
}

🍻 哈希优化

class Solution {public TreeNode buildTree(int[] inorder, int[] postorder) {int n = inorder.length;Map<Integer, Integer> index = new HashMap<>(n); // 预分配空间for (int i = 0; i < n; i++) {index.put(inorder[i], i);}return dfs(inorder, 0, n, postorder, 0, n, index); // 左闭右开区间}private TreeNode dfs(int[] inorder, int inL, int inR, int[] postorder, int postL, int postR, Map<Integer, Integer> index) {if (postL == postR) { // 空节点return null;}int leftSize = index.get(postorder[postR - 1]) - inL; // 左子树的大小TreeNode left = dfs(inorder, inL, inL + leftSize, postorder, postL, postL + leftSize, index);TreeNode right = dfs(inorder, inL + leftSize + 1, inR, postorder, postL + leftSize, postR - 1, index);return new TreeNode(postorder[postR - 1], left, right);}
}