判断平衡二叉树
问题链接：https://leetcode-cn.com/problems/balanced-binary-tree/
一、问题描述
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：true
示例 2：
输入：root = [1,2,2,3,3,null,null,4,4]
输出：false
示例 3：
输入：root = []
输出：true
提示：
树中的节点数在范围 [0, 5000] 内
-104 <= Node.val <= 104
二、问题分析
递归判断两个子树是否为平衡二叉树，只要有一个子树不平衡就不是平衡二叉树。如果是在判断当前根节点是否是平衡二叉树，如果平衡就返回当前子树高度给上层判断。
三、算法
1 /** 2 * Definition for a binary tree node. 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode() {} 8 * TreeNode(int val) { this.val = val; } 9 * TreeNode(int val, TreeNode left, TreeNode right) { 10 * this.val = val; 11 * this.left = left; 12 * this.right = right; 13 * } 14 * } 15 */ 16 class Solution { 17 public boolean isBalanced(TreeNode root) { 18 int flag = isBal(root); 19 if(flag == -1){ 20 return false; 21 } 22 return true; 23 } 24 25 public int isBal(TreeNode root){ 26 if(root == null){ 27 return 0; 28 } 29 int leftlayer = isBal(root.left); 30 int rightlayer = isBal(root.right); 31 if(leftlayer == -1 ||rightlayer == -1 || Math.abs(leftlayer-rightlayer)>1){ 32 return -1; 33 }else{ 34 return Math.max(leftlayer, rightlayer) + 1; 35 } 36 } 37 }
原文：https://www.cnblogs.com/zyq79434/p/15125763.html