有序数组构造平衡树
1、因为是有序数组，所以我们要取数组中间的数作为根节点
2、接下来我们可以将数组分成左右两块
3、根的左节点为左边的数组的中间的值，而根的右节点为右边数组的中间的值
4、左节点的左节点和右节点的右节点也同理，不断分割数组，直到数组的左边索引大于右边索引，数组值为空
点击查看代码
public class sortedArrayToBST {
public static void main(String[] args) {
int[] nums={-10,-3,0,5,9};
sortedArrayToBST s1=new sortedArrayToBST();
TreeNode root=s1.sortedArrayToBST(nums);
TreeNode node=root;
}
public TreeNode sortedArrayToBST(int[] nums) {
return helper(nums, 0, nums.length - 1);
}
private TreeNode helper(int[] nums, int left, int right) {
if (left > right) {
return null;
}
int mid = (left + right) / 2;
TreeNode root = new TreeNode(nums[mid]);
root.left = helper(nums, left, mid - 1);
root.right = helper(nums, mid + 1, right);
return root;
}
}
判断是否为平衡树
平衡树的性质：任何一个节点的左右节点深度差，绝对值小于1
1、声明两个方法，一个用来判断是否平衡，一个用来计算深度
2、平衡的条件：根的左右节点深度差绝对值小于等于1，且其左右节点也平衡
左右节点平衡的条件是其子节点平衡……不断重复
public boolean isBalanced(TreeNode root) {
//如果为空则是
if (root == null) return true;
//非空则判断左右子树的深度
return Math.abs(getDeepth(root.left) - getDeepth(root.right)) <= 1 && isbalanced(root.left) isbalanced(root.right); } < code></=>
3、计算深度的方法：
分别计算左右节点的深度，取最大的深度为该节点的深度
public int getDeepth(TreeNode node) {
if (node == null) {
return 0;
}
int right = getDeepth(node.right) + 1;
int left = getDeepth(node.left) + 1;
return Math.max(right, left);
}`
点击查看完整代码
public class isBalanced {
public boolean isBalanced(TreeNode root) {
//如果为空则是
if (root == null) return true;
//非空则判断左右子树的深度
return Math.abs(getDeepth(root.left) - getDeepth(root.right)) <= 1 && isbalanced(root.left) isbalanced(root.right); } 定义一个方法，得到左或右子树的深度 public int getdeepth(treenode node) { if (node="=" null) return 0; right="getDeepth(node.right)" + 1; left="getDeepth(node.left)" math.max(right, left); < code></=>
Original: https://www.cnblogs.com/MyJyang/p/15494901.html
Author: Jyang~
Title: 树
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/584664/
转载文章受原作者版权保护。转载请注明原作者出处！