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中的红黑树，我们经常了解到他的理论，没有实际代码编写能力，本文从理论出发，到实践编码来理解平衡二叉树，如果本文对你有帮助，希望可以得到您的关注，点赞，收藏。

关注我，一起学习最干的服务端技术。