leetcode110-平衡二叉树

前语

算法是核算机软件的基础，常见算法是软件开发的核心基本功，本年计划深化学习一些算法，记录一些算法理论以及最佳实践，希望可以坚持下去，重视我，咱们一同学习，增强咱们的基本功。

平衡二叉树界说

平衡二叉树的应用非常广泛，红黑树，b树都是平衡二叉树，咱们看下平衡二叉树的界说：

每个节点的左右子树高度差不超过1。

树的高度

什么是树的高度呢？

树节点的高度：叶子节点到该节点间的最长途径数。

算法题处理

虽然是一道简单题，可是要把代码编写出来不是很简单，需求了解遍历树的方法和代码逻辑。

由于平衡二叉树是指树的左右子树高度差不能为1，因而咱们需求求每个节点的高度，高度是节点到叶子节点的途径。 求高度需求从叶子节点往上遍历，因而咱们运用树的后序遍历,由于后续遍历是把每个节点左右子树先遍历完，再遍历自己，咱们想一想是不是这样。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isBalanced(TreeNode root) {
        int height = getHeight(root);
        if(height == -1) {
            return false;
        }
        return true;
    }
    int getHeight(TreeNode root) {
        if(root == null) {
            return 0;
        }
        //左子树高度
        int left = getHeight(root.left);
        if(left == -1) {
            return -1;
        }
        //右子树高度
        int right = getHeight(root.right);
        if(right == -1) {
            return -1;
        }
        //左右子树高度差
        int gap = Math.abs(left-right);
        if(gap >1) {
            return -1;
        }
        //核算当时节点的高度=取左右子树中最高高度+1
        return 1 + Math.max(left,right);
    }
}

整体思路便是依据后序遍历方法，求每个节点的左右子树高度，然后核算高度差，假如高度差大于1，直接回来-1（代表不是平衡二叉树），不然核算当时节点的高度=左右子树中最大高度+1，依次继续遍历二叉树，直到所有节点遍历完毕，只要高度值不是-1，代表是平衡二叉树，不然代表不是二叉树。

总结

平衡二叉树是运用比较多的数据结构，比如mysql的索引，HashMap中的红黑树，咱们常常了解到他的理论，没有实践代码编写才能，本文从理论动身，到实践编码来了解平衡二叉树，假如本文对你有帮助，希望可以得到您的重视，点赞，保藏。

重视我，一同学习最干的服务端技术。