Java构建完全二叉树 递归
时间: 2023-10-23 09:27:39 浏览: 32
下面是Java语言实现递归构建完全二叉树的代码:
```java
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class Solution {
public TreeNode buildTree(int[] nums) {
return buildTree(nums, 0, nums.length - 1);
}
private TreeNode buildTree(int[] nums, int start, int end) {
if (start > end) return null;
int mid = (start + end) / 2;
TreeNode root = new TreeNode(nums[mid]);
root.left = buildTree(nums, start, mid - 1);
root.right = buildTree(nums, mid + 1, end);
return root;
}
}
```
其中,`buildTree`方法接收一个整型数组`nums`作为参数,返回构建出的完全二叉树的根节点。`buildTree`方法调用递归函数`buildTree`进行完全二叉树的构建,递归函数接收一个整型数组`nums`、一个起始下标`start`和一个终止下标`end`作为参数,返回构建出的完全二叉树的根节点。
在递归函数中,首先判断起始下标`start`是否大于终止下标`end`,如果成立则返回`null`。否则,计算出当前子数组的中间位置`mid`,以`mid`位置的元素为根节点构建出一棵二叉树,并递归调用`buildTree`方法构建出当前节点的左右子树。最后返回构建出的二叉树的根节点。