63. 平衡二叉树

❝

这是一道 「简单」 题
https://leetcode.cn/problems/balanced-binary-tree/

❞

题目

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

本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 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] 内

题解

根据题意，要求得是否是平衡树就势必要求得每个节点的高度，并计算左右节点高度差是否大于1。

那么我们可以将题目拆分成两部分:

第一步先求得各个节点的高度，
然后第二步再根据高度判断是否平衡。

一、求高度：

要求得一个节点的高度，必须得求得其左右子节点的高度，然后取最大值并加一。求子节点的高度是一个「子问题」，所以可以使用「递归」的思路。

递归边界：当遇到的节点为空时，直接返回高度为0。

以 Java 为例，递归函数可以定义为：

private int dfs(TreeNode root){
    if(root == null){
        return 0;
    }

    // 子问题
    int leftHeight = dfs(root.left);
    int rightHeight = dfs(root.right);

    return Math.max(leftHeight, rightHeight) + 1;
}

二、判断是否平衡

在上一步求得高度的同时，我们就可以顺便从下往上求得每个子树是否平衡。

我们假设不平衡树的高度为 -1 。那么只要其左右子树高度差大于1 或者左右子树中任意一个的高度是 -1，那么这棵树就是不平衡的，否则就是平衡的。详见代码实现。

代码实现

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) {
        return dfs(root) != -1;
    }

    // 返回树的深度
    private int dfs(TreeNode root){
        if(root == null){
            return 0;
        }

        int leftHeight = dfs(root.left);
        int rightHeight = dfs(root.right);

        if(leftHeight == -1 || rightHeight == -1 || Math.abs(leftHeight - rightHeight) > 1){
            return -1;
        }

        return Math.max(leftHeight, rightHeight) + 1;
    }
}

Go

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isBalanced(root *TreeNode) bool {

    var dfs func(node *TreeNode) int

    dfs = func(node *TreeNode) int {
        if node == nil {
            return 0
        }

        leftHeight := dfs(node.Left)
        rightHeight := dfs(node.Right)

        if leftHeight == -1 || rightHeight == -1 || leftHeight - rightHeight > 1 || rightHeight - leftHeight > 1 {
            return -1
        }

        if leftHeight > rightHeight {
            return leftHeight + 1
        }else {
            return rightHeight + 1
        }
    }

    return dfs(root) != -1

}