手撸二叉树之平衡二叉树

Hello, 大家好，今天给大家带来的有关二叉树的算法题为平衡二叉树，正文如下。

题目：

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

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

解题思路

这里强调一波概念：

• 二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数
• 二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数

当求二叉树的高度，我们可以使用自底向上的递归方式，自底向上递归的做法类似于后序遍历。

递归分析：

1. 明确递归函数的参数和返回值

参数为传入的节点，返回值要返回传入节点为根节点树的深度
那么如何标记左右子树是否差值大于1呢。
如果当前传入节点为根节点的二叉树已经不是二叉平衡树了，还返回高度的话就没有意义了。
所以如果已经不是二叉平衡树了，可以返回-1 来标记已经不符合平衡树的规则了。

2. 明确终止条件

递归的过程中依然是遇到空节点了为终止，返回0，表示当前节点为根节点的高度为0

3. 明确单层递归的逻辑

如何判断当前传入节点为根节点的二叉树是否是平衡二叉树呢，当然是左子树高度和右子树高度之差。

分别求出左右子树的高度，如果差值小于等于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) {
    //     return height(root) >= 0;
    // }

    // public int height(TreeNode root) {
    //     if (root == null) return 0;
    //     int leftHeight = height(root.left);
    //     if (leftHeight == -1) return -1;

    //     int rightHeight = height(root.right);
    //     if (rightHeight == -1) return -1;

    //     return Math.abs(leftHeight - rightHeight) > 1 ? -1 : Math.max(leftHeight, rightHeight) + 1;  
    // }

    // 更利于理解的思路
    private static final int UNBALANCED = -1;

    public boolean isBalanced(TreeNode root) {
        return helper(root) != UNBALANCED;
    }

    public int helper(TreeNode root) {
        if (root == null) {
            return 0;
        }

        // 如果左子树不是平衡二叉树，直接返回UNBALANCED
        int left = helper(root.left);
        if (left == UNBALANCED) {
            return UNBALANCED;
        } 

        // 如果右子树不是平衡二叉树，直接返回UNBALANCED
        int right = helper(root.right);
        if (right == UNBALANCED) {
            return UNBALANCED;
        }

        // 如果左右子树是平衡二叉树，但是他们的高度相差大于1，直接返回UNBALANCED
        if (Math.abs(left - right) > 1) {
            return UNBALANCED;
        }

        // 否则就返回二叉树中节点的最大高度
        return Math.max(left, right) + 1;
    }
}

最后

复杂度分析

时间复杂度：O(n)，其中 n 是二叉树中的节点个数。使用自底向上的递归，每个节点的计算高度和判断是否平衡都只需要处理一次，最坏情况下需要遍历二叉树中的所有节点，因此时间复杂度是 O(n)。

空间复杂度：O(n)，其中 n 是二叉树中的节点个数。空间复杂度主要取决于递归调用的层数，递归调用的层数不会超过 n。