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

题目描述

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

分析

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

直接思路：由于可以方便地递归计算二叉树的深度（参见文章)。按照AVL树的定义，顺序遍历二叉树的每一个节点，分别计算左右子树的深度，判断深度是否相差1；如果不是，直接返回false，否则递归判断该节点的左子节点和右子节点。但是该算法有一个问题，从上往下递归遍历计算每一个节点的深度时，有很多节点会发生重复遍历，越深层次的重复遍历次数越高，因此会影响性能。

代码：

public boolean IsBalanced_Solution(TreeNode root) {        if(root == null)            return true;        int leftDepth = TreeDepth(root.left);        int rightDepth = TreeDepth(root.right);        int diffDepth = leftDepth - rightDepth;        if(diffDepth < -1 || diffDepth > 1)            return false;        return IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);    }    public int TreeDepth(TreeNode root) {        if(root == null)            return 0;        else             return max(TreeDepth(root.left), TreeDepth(root.right)) + 1;    }    public int max(int num1, int num2) {        return (num1 > num2) ? num1 : num2;    }

推荐解法

后序遍历，左右根，判断每个节点是否是平衡节点。当遍历到一个根节点时，先遍历该根节点的左右子树，计算左右子树的深度并通过传址的方式进行向上传递；如果该根节点是平衡节点，则向上遍历该节点的父亲节点，父亲节点的深度在之前传递的深度基础上加1即可，因此避免了深度计算中的节点重复遍历，提高了效率。

后序遍历适用于对二叉树进行“自底向上”的操作。

牛客AC：

package com.problem;/** * 输入一棵二叉树，判断该二叉树是否是平衡二叉树。 *  * key: 后续遍历的方法，避免重复遍历节点 *  *  * @author Administrator * */public class BalancedBinaryTree {
       class TreeNode {        int val = 0;        TreeNode left = null;        TreeNode right = null;        public TreeNode(int val) {            this.val = val;        }    }    public boolean IsBalanced_Solution(TreeNode root) {        int[] depth = {
  0};        return isBalancedTree(root, depth);    }    /**     *      * @param root  根节点     * @param depth 深度，数组传址参数，需要在函数调用后改变depth，参与运算     *              类似于c++中的引用参数     * @return     */    public boolean isBalancedTree(TreeNode root, int[] depth) {        if(root == null) {            depth[0] = 0;            return true;        }        // 数组传址参数，用于传递函数调用后的数据，参与运算        int[] leftDepth = {
  0};        int[] rightDepth = {
  0};        // 后续遍历，左右根，判断每个节点是否是平衡节点        // 当遍历到一个根节点时，先遍历该根节点的左右子树，计算左右子树的深度并通过        // 传址的方式进行向上传递；如果该根节点是平衡节点，则向上遍历该节点的父亲节点，        // 父亲节点的深度在之前传递的深度基础上加1即可，        // 因此避免了深度计算中的节点重复遍历，提高了效率        if(isBalancedTree(root.left, leftDepth) && isBalancedTree(root.right, rightDepth)) {            int diffDepth = leftDepth[0] - rightDepth[0];            if(diffDepth >= - 1 && diffDepth <= 1) {                int tmpDepth = (leftDepth[0] > rightDepth[0]) ? leftDepth[0] : rightDepth[0];                depth[0] = 1 + tmpDepth;                return true;            }        }        return false;    }}

参考

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