平衡二叉树

题目

力扣第 110 题，平衡二叉树。给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

示例1:

输入：root = [3,9,20,null,null,15,7]
输出：true

示例2:

输入：root = [1,2,2,3,3,null,null,4,4]
输出：false

示例3:

输入：root = []
输出：true

提示：

• 树中的节点数在范围 [0, 5000] 内
• -104 <= Node.val <= 104

思路

本题中，平衡二叉树的特点是每个节点的左右两边子树的高度差不能超过 1，所以最简单有效的办法就是分别求出每个节点的左右子树的高度差。如果高度差大于 1 就返回 false。如果所有的情况下高度差小于等于 1。那么就返回 true。

熟悉树结构的情况都同学都清楚，解决树的遍历就需要用到递归，我们就具体的情况来分析一下。

示例1：遍历 [3,9,20,null,null,15,7] 树结构：

因为使用的是递归调用，判断每一个节点的子树的高度，所以我们会从叶子结点开始，逐个判断其左右节点高度：

这边在计算每个节点的左右节点的高度的时候，是从末节点开始计算。计算步骤如下：

• 第一步：计算 9 节点的左子树高度 0 ，右子树高度 0。两个高度相差为 0 。符合条件。
• 第二步：计算 15 节点的高度差，左子树高度 0，右子树高度0。两个高度相差为 0。符合条件。
• 第三步：计算 7 节点的高度差，左右子树高度都为 0。符合条件
• 第四步：计算 20 节点的高度差，左子树高度 1，右子树高度 1。两个高度差为 0，符合条件。
• 第五步：计算 3 节点的高度差，左子树高度 1，右子树高度为 2，两个高度差为 1。符合条件。

因为每个节点的高度差都计算过了，符合条件，所以返回 true。

示例2：遍历[1,2,2,3,3,null,null,4,4] 结构：

和上面的计算步骤一样，也是从底往上计算，分别计算每个节点的左右子树的高度差：

• 第一步：计算左边的节点 4 的子树高度差，左右节点子树高度都是 0。符合条件。
• 第二步：计算右边的节点 4 的子树高度差，左右子节点高度都是 0。符合条件。
• 第三步：计算左边的节点 3 的子树高度差，左右子节点的高度都是 1 ，符合条件。
• 第四步：计算右边的节点 3 的子树高度差，左右子节点的高度都是 0 ，符合条件。
• 第五步：计算左边节点 2 的子树高度差，左子节点高度 2，右子节点高度 1，高度差为 1，符合条件。
• 第六步：计算右边节点 2 的子树高度差，左右节点的高度为 0。高度差为 0，符合条件。
• 第七步：计算节点 1 的子树高度差，左子节点高度 3，右子节点高度 1，高度差为 2，不符合条件。

在计算最后一个节点的高度差的时候，返回高度差为 2，所以不符合条件，返回 false。

代码具体实现

Java语言版本

/**
 * 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) {
        if(root == null){
            return true;
        }
        if(!isBalanced(root.left)){//如果左子树不平衡返回false
            return false;
        }
        if(!isBalanced(root.right)){//如果右子树不平衡返回false
            return false;
        }
        int leftHeight =getHeight(root.left);
        int rightHeight = getHeight(root.right);
        if(leftHeight - rightHeight <= 1 && leftHeight - rightHeight >= -1 ){
            return true;
        }
          return false;
    }
    //计算节点高度
    private int getHeight(TreeNode node){
        if(node == null){
            return 0;
        }
        int leftheight = getHeight(node.left);
        int rightHeight = getHeight(node.right);
        return leftheight > rightHeight ? leftheight + 1 : rightHeight + 1 ;
    }
}

Go语言版本

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isBalanced(root *TreeNode) bool {
    if root == nil {
            return true
        }
        if !isBalanced(root.Left) {//如果左子树不平衡返回false
            return false
        }
        if !isBalanced(root.Right) {//如果右子树不平衡返回false
            return false
        }
        leftHeight := getHeight(root.Left)
        rightHeight := getHeight(root.Right)
        if leftHeight - rightHeight <= 1 && leftHeight - rightHeight >= -1 {
            return true
        }
        return false
    }
    //计算节点高度
    func getHeight(node *TreeNode) int{
        if node == nil {
            return 0;
        }
        leftheight := getHeight(node.Left)
        rightHeight := getHeight(node.Right)
        if leftheight > rightHeight {
            return  leftheight + 1
        } else {
            return rightHeight + 1
        }
    }