根据先序和中序确定树java
时间: 2024-02-14 14:02:59 浏览: 18
可以使用递归的方式来根据先序和中序遍历结果构建一棵二叉树。具体步骤如下:
1. 首先,先序遍历的第一个节点一定是根节点,从中序遍历中找到根节点的位置。
2. 以根节点在中序遍历中的位置为分界点,将中序遍历结果分成左子树和右子树两部分。
3. 计算出左子树的节点个数,以此在先序遍历结果中区分出左子树和右子树。
4. 递归构建左子树和右子树。
下面是具体的 Java 代码实现:
```
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
return build(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
}
private TreeNode build(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd) {
if (preStart > preEnd || inStart > inEnd) {
return null;
}
int rootVal = preorder[preStart];
TreeNode root = new TreeNode(rootVal);
int rootIndex = 0;
for (int i = inStart; i <= inEnd; i++) {
if (inorder[i] == rootVal) {
rootIndex = i;
break;
}
}
int leftSize = rootIndex - inStart;
root.left = build(preorder, preStart + 1, preStart + leftSize, inorder, inStart, rootIndex - 1);
root.right = build(preorder, preStart + leftSize + 1, preEnd, inorder, rootIndex + 1, inEnd);
return root;
}
}
```
其中,`buildTree` 方法接收先序遍历结果和中序遍历结果,返回构建好的根节点。`build` 方法实现了递归构建子树的过程。在 `build` 方法中,先根据先序遍历结果找到根节点的值,然后在中序遍历结果中找到根节点的位置,以此计算出左子树的节点个数。最后,递归构建左子树和右子树。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)