一、题目
1、审题
2、分析
给出一棵二叉树，判断其是否是一棵二叉平衡树。
二、解答
1、思路：
方法一、
采用递归；
每次获取 root 结点的左子树、右子树的高度，比较高度差是否小于等于 1；
同时判断左子树、右子树是否也是二叉平衡树。
public boolean isBalanced(TreeNode root) { if(root == null) return true; int left = getDepthHelper(root.left); int right = getDepthHelper(root.right); return Math.abs(left - right) <= 1 && isBalanced(root.left) && isBalanced(root.right); } private int getDepthHelper(TreeNode root) { if(root == null) return 0; return Math.max(getDepthHelper(root.left), getDepthHelper(root.right)) + 1; }
方法二、
采用深度优先遍历的方式获取深度，并且获取时比较该节点的子树是否平衡，若不平衡，返回 -1，否则返回高度。
public boolean isBalanced(TreeNode root) { return dfsHeight(root) != -1; } private int dfsHeight(TreeNode root) { if(root == null) return 0; int leftHeight = dfsHeight(root.left); if(leftHeight == -1) return -1; int rightHeight = dfsHeight(root.right); if(rightHeight == -1) return -1; if(Math.abs(leftHeight - rightHeight) > 1) return -1; return Math.max(leftHeight, rightHeight) + 1; }
原文：https://www.cnblogs.com/skillking/p/9734889.html