本文共 1328 字，大约阅读时间需要 4 分钟。

1. 本题知识点

树

2. 题目描述

输入一棵二叉树，判断该二叉树是否是平衡二叉树。

在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树。

平衡二叉树（Balanced Binary Tree），具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过 1，并且左右两个子树都是一棵平衡二叉树。

例如：

输入:{1,2,3,4,5,6,7}返回值：true

3. 解题思路

利用后序遍历：左子树、右子树、根节点，可以先递归到叶子节点，然后在回溯的过程中来判断是否满足条件。

4. 代码

public class TreeNode {
       int val = 0;    TreeNode left = null;    TreeNode right = null;    public TreeNode(int val) {
           this.val = val;    }}

public class Solution {
       public boolean isBalanced_Solution(TreeNode root) {
           // 它是一棵空树，则是平衡的        if (root == null) {
               return true;        }        int depth = getDepth(root);        if (depth == -1) {
               return false;        }        return true;    }    /**     * 返回当前节点的深度     * @param root     * @return     */    public int getDepth(TreeNode root) {
           // 叶节点深度为 0        if (root == null) {
               return 0;        }        int left = getDepth(root.left);        // 遍历过程中发现子树不平衡        if (left == -1) {
               return -1;        }        int right = getDepth(root.right);        // 遍历过程中发现子树不平衡        if (right == -1) {
               return -1;        }        // 左右两个子树的高度差的绝对值超过 1，则不平衡        if (Math.abs(left - right) > 1) {
               return -1;        }        // 返回当前节点的深度        return left > right ? left + 1 : right + 1;    }}

转载地址：http://objvb.baihongyu.com/