力扣105.从前序与中序遍历序列构造二叉树
力扣105.从前序与中序遍历序列构造二叉树
老规矩，上原题链接和题目描述：
原题会给出两个数组，分别是原二叉树的前序遍历和中序遍历的结果。我们需要根据这两个数组来构造出原二叉树。
解法一
其实这个题一上来我是真一点思路没有🤡🤡🤡，没招，你给我这两个遍历结果，我人肉去构建都得看半天，并且我没有固定的方法，一直都是瞪眼法🤡🤡🤡。我实在没招了，就去看了一眼解答的提示，看了开头，提示我可以把根节点找出来，左右子树根据中序遍历就有了。我感觉一下就有思路了。直接使用递归去分治解决。于是我直接趁热打铁写下了如下代码：
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
TreeNode root = new TreeNode(preorder[0]);
for (int i = 0; i < inorder.length; i++) {
if (inorder[i] == preorder[0]) {
if (i == 0) {
root.left = null;
} else {
root.left = buildTree2(preorder, inorder, 1, 1 + i - 1,
0, i - 1);
}
root.right = buildTree2(preorder, inorder, i + 1, inorder.length - 1,
i + 1, inorder.length - 1);
break;
}
}
return root;
}
public TreeNode buildTree2(int[] preorder, int[] inorder, int preorderStart, int preorderEnd, int inorderStart, int inorderEnd) {
if (inorderStart > inorderEnd || inorderStart < 0 ||
inorderEnd >= inorder.length || preorderStart < 0 ||
preorderEnd >= preorder.length|| preorderStart > preorderEnd) {
return null;
}
if (preorderStart == preorderEnd) {
return new TreeNode(preorder[preorderStart]);
}
TreeNode root = new TreeNode(preorder[preorderStart]);
for (int i = inorderStart; i <= inorderEnd; i++) {
if (inorder[i] == preorder[preorderStart]) {
int leftLen = i - inorderStart;
if (i == inorderStart) {
root.left = null;
} else {
root.left = buildTree2(preorder, inorder, preorderStart + 1, preorderStart + leftLen,
inorderStart, i - 1);
}
root.right = buildTree2(preorder, inorder, preorderStart + leftLen + 1, preorderEnd,
i + 1, inorderEnd);
break;
}
}
return root;
}
}
提交一次过💪💪💪，一看效率，打败百分之30不到🤡🤡🤡。没招，继续优化。
解法二
注意到题目中提到没有重复节点。上面的代码中我们使用的是循环去手动寻找下标。于是稍微修改，很容易得出下面的解法：
class Solution {
private HashMap<Integer, Integer> inorderMap = new HashMap<>();
public TreeNode buildTree(int[] preorder, int[] inorder) {
for (int i = 0; i < inorder.length; i++) {
inorderMap.put(inorder[i], i);
}
TreeNode root = new TreeNode(preorder[0]);
int i=inorderMap.get(preorder[0]);
if (i == 0) {
root.left = null;
} else {
root.left = buildTree2(preorder, inorder, 1, 1 + i - 1,
0, i - 1);
}
root.right = buildTree2(preorder, inorder, i + 1, inorder.length - 1,
i + 1, inorder.length - 1);
return root;
}
public TreeNode buildTree2(int[] preorder, int[] inorder, int preorderStart, int preorderEnd, int inorderStart, int inorderEnd) {
if (inorderStart > inorderEnd || inorderStart < 0 ||
inorderEnd >= inorder.length || preorderStart < 0 ||
preorderEnd >= preorder.length|| preorderStart > preorderEnd) {
return null;
}
if (preorderStart == preorderEnd) {
return new TreeNode(preorder[preorderStart]);
}
TreeNode root = new TreeNode(preorder[preorderStart]);
int i=inorderMap.get(preorder[preorderStart]);
int leftLen = i - inorderStart;
if (i == inorderStart) {
root.left = null;
} else {
root.left = buildTree2(preorder, inorder, preorderStart + 1, preorderStart + leftLen,
inorderStart, i - 1);
}
root.right = buildTree2(preorder, inorder, preorderStart + leftLen + 1, preorderEnd,
i + 1, inorderEnd);
return root;
}
}
哈希表yyds，直接干倒百分之99。原题解答还提供了迭代解法，感觉也不错，大家可以去看看，我就懒得写了。
力扣105.从前序与中序遍历序列构造二叉树
https://www.than.pw/archives/%E5%8A%9B%E6%89%A3105.%E4%BB%8E%E5%89%8D%E5%BA%8F%E4%B8%8E%E4%B8%AD%E5%BA%8F%E9%81%8D%E5%8E%86%E5%BA%8F%E5%88%97%E6%9E%84%E9%80%A0%E4%BA%8C%E5%8F%89%E6%A0%91