用Java写出重建二叉树
时间: 2023-02-22 13:43:39 浏览: 50
在Java中重建二叉树的方法如下:
首先,需要定义二叉树节点的结构,可以使用以下代码:
```
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
```
然后,可以使用前序遍历和中序遍历的方法重建二叉树,实现代码如下:
```
public TreeNode buildTree(int[] preorder, int[] inorder) {
return helper(0, 0, inorder.length - 1, preorder, inorder);
}
public TreeNode helper(int preStart, int inStart, int inEnd, int[] preorder, int[] inorder) {
if (preStart > preorder.length - 1 || inStart > inEnd) {
return null;
}
TreeNode root = new TreeNode(preorder[preStart]);
int inIndex = 0; // Index of current root in inorder
for (int i = inStart; i <= inEnd; i++) {
if (inorder[i] == root.val) {
inIndex = i;
}
}
root.left = helper(preStart + 1, inStart, inIndex - 1, preorder, inorder);
root.right = helper(preStart + inIndex - inStart + 1, inIndex + 1, inEnd, preorder, inorder);
return root;
}
```
以上代码实现了递归地构建二叉树,每次通过前序遍历找到当前节点,并根据中序遍历找到左右子树的范围,递归构建左右子树。