【算法】平衡二叉树110

描述

110. 平衡二叉树 - 力扣（Leetcode）

分析

-1 表示已经不是平衡二叉树了，否则返回值是以该节点为根节点树的高度

实现

import java.lang.Math;

//110.平衡二叉树
public class BalancedBinaryTree110 {
	public static void main(String[] args){
		//TreeNode root = MyUtils.buildTree(new Integer[]{3,9,20,null,null,15,7});
		TreeNode root = MyUtils.buildTree(new Integer[]{1,2,2,3,3,null,null,4,4});

		if (new Solution().isBalanced(root)) {
			System.out.println("这是个平衡二叉树");
		}else{
			System.out.println("no");
		}
	}
}
class Solution {
    public boolean isBalanced(TreeNode root) {
    	return getHeight(root) != -1;
    }
    //返回以root为父节点的子树的高度，如果为-1就是这是一颗不平衡的二叉树
    private int getHeight(TreeNode root){

    	if(root == null) return 0;
    	//如果左右子树有一个是不平衡的，那以root为父节点的树坑定是不平衡的。
    	int leftHeight = getHeight(root.left);
    	if (leftHeight == -1) return -1;
    	int rightHeight = getHeight(root.right);
    	if (rightHeight == -1) return -1;
    	//如果左右子树都是平衡二叉树，只有他们高度差 > 1才是非平衡二叉树
    	if (Math.abs(rightHeight - leftHeight) > 1) return -1;
    	//确认了我这棵树就是平衡二叉树那就直接说我的高度是多少
    	return Math.max(rightHeight, leftHeight) + 1;
    }

}

class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;

	public TreeNode(){};
	public TreeNode(int val){this.val = val;}
	public TreeNode(int val, TreeNode left, TreeNode right){
		this.val = val;
		this.left = left;
		this.right = right;
	}
}


class MyUtils {
	/**
	 *二叉树的构建
	 * int[] -> 二叉树
	 */
	 public static TreeNode buildTree(Integer[] arr) {
        return buildTreeHelper(arr, 0);
    }

    public static TreeNode buildTreeHelper(Integer[] arr, Integer index) {
        if (index >= arr.length || arr[index] == null) {
            return null;
        }

        TreeNode node = new TreeNode(arr[index]);

        node.left = buildTreeHelper(arr, 2 * index + 1);
        node.right = buildTreeHelper(arr, 2 * index + 2);

        return node;
    }
}

总结