用java语言实现以下代码:给定两个整数数组 preorder 和 inorder ,其中 preorder 是二叉树的先序遍历, inorder 是同一棵树的中序遍历,请构造二叉树并返回其根节点。
时间: 2023-12-22 17:49:37 浏览: 78
以下是用 Java 实现给定先序遍历和中序遍历构造二叉树的代码:
```
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
}
}
public class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder == null || inorder == null || preorder.length != inorder.length) {
return null;
}
return buildTree(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
}
private TreeNode buildTree(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd) {
if (preStart > preEnd || inStart > inEnd) {
return null;
}
int rootValue = preorder[preStart];
int rootIndex = 0;
for (int i = inStart; i <= inEnd; i++) {
if (inorder[i] == rootValue) {
rootIndex = i;
break;
}
}
TreeNode root = new TreeNode(rootValue);
int leftSize = rootIndex - inStart;
root.left = buildTree(preorder, preStart + 1, preStart + leftSize, inorder, inStart, rootIndex - 1);
root.right = buildTree(preorder, preStart + leftSize + 1, preEnd, inorder, rootIndex + 1, inEnd);
return root;
}
}
```
在这个代码中,我们首先判断是否存在先序遍历和中序遍历,以及它们的长度是否相等,如果不符合条件则直接返回 null。如果它们符合条件,则我们调用递归函数 buildTree 来构造二叉树。在递归函数中,我们首先判断是否到达了叶子节点,如果是则返回 null。然后我们取出当前子树的根节点,并在中序遍历中找到它的位置,根据它的位置我们可以计算出左子树的大小,然后递归构造左子树和右子树,最后返回根节点即可。
阅读全文