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

声明：

作者不是什么大佬，只是想写写算法，提高一下自己的内功。所以代码可能会非常凌乱，（大佬们就当个笑话看就可以了），但我会认真注释。

---

最后如果有路过的大佬，希望可以留下你们的建议和看法，谢谢！

110.平衡二叉树

一、原题链接

二、题目介绍

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。

三、测试用例

1.示例

给定二叉树 [3,9,20,null,null,15,7]

输出: true

2.示例

给定二叉树 [1,2,2,3,3,null,null,4,4]

输出: false

四、思路解析

个人认为这道题考察的是：树的层次遍历和数的深度遍历，毕竟我是通过这种依次判断的方式进行暴力破解。挺适合递归入门或是树算法的入门的

• 通过使用队列的特性进行遍历并保存树的层次结构，用于接下来自上而下地遍历每个结点
• 树的深度遍历
  这个深度遍历的时候要注意，不要被子树的分支所迷惑，我们的目的是找到当前子树的最深层次。
  举例

  

  这个是对A进行遍历：代码的实现下面有。本算法是通过本逻辑获取结点左右子树的深度，进行判断的。每个结点都要进行

五、代码

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */class Solution {
       /**     * 用于层次遍历的队列     */    LinkedQueue linkedQueue = new LinkedQueue();    QueueElem cur;    /**     * 层次遍历，并将结果保存到队列里面     *     * @param treeNode     */    public void touchNode(TreeNode treeNode) {
           if (cur != null && cur.val == treeNode) {
           } else {
               linkedQueue.put(treeNode);        }        if (treeNode.left != null) {
               linkedQueue.put(treeNode.left);        }        if (treeNode.right != null) {
               linkedQueue.put(treeNode.right);        }        if (cur == null) {
               cur = linkedQueue.head;        }        cur = cur.next;        if (cur != null) {
               touchNode(cur.val);        } else {
               return;        }    }    /**     * 获取当前结点的深度（重点）     *     * @param curNode     * @return     */    public int getheigh(TreeNode curNode) {
           // 用于保存左右子树深度，返回大的        int ri = 0;        int le = 0;        // 如果无左右子树，返回0        if (curNode.right == null && curNode.left == null) {
               return 0;        }        // 无论左右子树有哪个都需要进入该数进行遍历并+1        // 通过+1的递归，可以起到累加的作用        if (curNode.left != null) {
               le = 1 + getheigh(curNode.left);        }        if (curNode.right != null) {
               ri = 1 + getheigh(curNode.right);        }        // 算是遍历完了当前结点的左右子树返回大的数值        return ri > le ? ri : le;    }    /**     * 只判断当前结点的左右子树的深度情况     *     * @param curNode     * @return     */    public boolean judge(TreeNode curNode) {
       	// 如果为空直接返回true        if (curNode == null) {
               return true;        }        // 获取左子树的深度        int left = curNode.left == null ? 0 : 1+getheigh(curNode.left);        // 获取右子树的深度        int right = curNode.right == null ? 0 : 1+getheigh(curNode.right);		// 取差判断当前结点是否满足平衡二叉树        int cha = right - left;        System.out.println(curNode.val + "  " + left + "  " + right);        if (cha <= -2 || cha >= 2) {
               return false;        }        return true;    }    public boolean isBalanced(TreeNode root) {
       	// 如果为空直接返回true        if(root == null){
               return true;        }        // 保存此树的层次遍历的结果        this.touchNode(root);        QueueElem cur = linkedQueue.head;		// 遍历队列，依次判断当前结点是否满足平衡二叉树，不满足直接返回false        while (cur != null) {
               if (!judge(cur.val)) {
                   return false;            }            cur = cur.next;        }        return true;    }}// 队列元素class QueueElem {
       TreeNode val;    QueueElem next;    QueueElem pre;    public QueueElem(TreeNode val) {
           this.val = val;    }}// 链表队列class LinkedQueue {
       QueueElem head;    QueueElem last;    void put(TreeNode treeNode) {
           // 封装        QueueElem queueElem = new QueueElem(treeNode);        // 添加        if (head == null) {
               head = queueElem;            last = queueElem;        } else {
               queueElem.pre = last;            last.next = queueElem;            last = queueElem;        }    }    // 删除    TreeNode remove() {
           if (head == null) {
               return null;        }        if (head == last) {
               TreeNode temp = head.val;            head = last = null;            return temp;        } else {
               TreeNode temp = head.val;            head.next.pre = null;            head = head.next;            return temp;        }    }}

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