题解 | #判断是不是平衡二叉树#

秒懂【平衡二叉树判断】！超清晰图解一步步拆解。

1.思路

先来看平衡二叉树的性质：

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

因此可以借助二叉树的高度来判断是否为平衡二叉树。整体思路为：先计算左右子树的高度，再比较左右子树的高度差（如果高度差大于1，则不是平衡二叉树）。

①对每一个节点的左右子树进行比较；②如果左子树不是平衡二叉树，就没有必要对右子树进行是否平衡的判断；③采用递归的方式对左右子树进行判断。

由于要采用递归来实现平衡二叉树的判断，因此需要验证是否满足递归的两个条件：

alt

可以看出，求解二叉树平衡性的判断满足递归的两个条件，因此可以采用递归的方法来求解。由于平衡性的判断依赖于二叉树的高度，二叉树的高度求解参考前序文章《可视化图解算法25：二叉树的最大深度（高度）》，二叉树高度求解对应的递推公式如下：

alt

接下来就可以依据二叉树的高度进行平衡性的判断，先求解二叉树的左右子树的高度，再判断左右子树高度差是否超过1，如果超过1则不是平衡二叉树。

如果文字描述的不太清楚，你可以参考视频的详细讲解：B站@好易学数据结构

2.代码

2.1 Python代码

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param pRoot TreeNode类
# @return bool布尔型
#
class Solution:
    is_balanced = True

    def IsBalanced_Solution(self, pRoot: TreeNode) -> bool:
        # write code here
        self.treeDepth(pRoot)
        return self.is_balanced

    def treeDepth(self, root):
        # 2. 递归终止条件
        if root is None:
            return 0

        #  1. 问题分解（递推公式）
        #  1.1 求解左子树的高度
        left = self.treeDepth(root.left)
        #  1.2 求解右子树的高度
        right = self.treeDepth(root.right)

        if abs(left - right) > 1:
            self.is_balanced = False  # 不是平衡树,更改全局变量
            return -1  # 加一个标记-1，已经不可能是平衡树了（减少递归计算次数）,直接返回

        # 1.3  求解当前树的高度
        dep = max(left, right) + 1
        return dep

2.2 Java代码

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param pRoot TreeNode类
     * @return bool布尔型
     */
    public boolean IsBalanced_Solution (TreeNode pRoot) {
        // write code here
        treeDepth(pRoot);
        return isBalanced;
    }

    boolean isBalanced = true;

    private int treeDepth(TreeNode root) {
        // 2. 递归终止条件
        if (root == null) {
            return 0;
        }

        // 1. 问题分解（递推公式）
        // 1.1 求解左子树的高度
        int left = treeDepth(root.left);
        // 1.2 求解右子树的高度
        int right = treeDepth(root.right);

        if (Math.abs(left - right) > 1) {
            isBalanced = false; // 不是平衡树,更改全局变量
            return -1;  // 加一个标记-1，已经不可能是平衡树了（减少递归计算次数）,直接返回
        }

        // 1.3 求解当前树的高度
        int dep = Math.max(left, right) + 1; //左右子树高度的最大值 加 1
        return dep;
    }
}

2.3 Go代码

package main

import (
	"math"
)

import . "nc_tools"

/*
 * type TreeNode struct {
 *   Val int
 *   Left *TreeNode
 *   Right *TreeNode
 * }
 */

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param pRoot TreeNode类
 * @return bool布尔型
 */
func IsBalanced_Solution(pRoot *TreeNode) bool {
	// write code here
	treeDepth(pRoot)
	return isBalanced
}

var isBalanced = true

func treeDepth(root *TreeNode) int {
	// 2. 递归终止条件
	if root == nil {
		return 0
	}

	// 1. 问题分解
	// 1.1 求解左子树的高度
	l := treeDepth(root.Left)
	// 1.2 求解右子树的高度
	r := treeDepth(root.Right)

	if math.Abs(float64(l-r)) > 1 {
		isBalanced = false // 不是平衡树,更改全局变量
		return -1          // 加一个标记-1，已经不可能是平衡树了（减少递归计算次数）,直接返回
	}
	// 1.3 求解当前树的高度
	dep := math.Max(float64(l), float64(r)) + 1
	return int(dep)
}

如果上面的代码理解的不是很清楚，你可以参考视频的详细讲解：B站@好易学数据结构