LeetCode 剑指 Offer 55 - II. 平衡二叉树

Categories:

题目描述
思路分析
1. 解法一：后序剪枝（推荐）
相似题目

题目描述

✅ 剑指 Offer 55 - II. 平衡二叉树

思路分析

解法一：后序剪枝（推荐）

核心思路：

递归计算子树高度，若发现某子树不平衡则返回 -1。

当前节点若左右高度差超过 1，也返回 -1。

最终根节点高度不为 -1 即为平衡二叉树。

复杂度分析：

时间复杂度：O(n)，其中 n 表示节点数，每个节点只访问一次。

空间复杂度：O(h)，其中 h 表示树高，递归栈空间。

class Solution {
    public boolean isBalanced(TreeNode root) {
        return height(root) != -1;
    }

    private int height(TreeNode node) {
        if (node == null) {
            return 0;
        }

        int left = height(node.left);
        if (left == -1) {
            return -1;
        }

        int right = height(node.right);
        if (right == -1) {
            return -1;
        }

        if (Math.abs(left - right) > 1) {
            return -1;
        }

        return Math.max(left, right) + 1;
    }
}

func isBalanced(root *TreeNode) bool {
	return height(root) != -1
}

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

	left := height(node.Left)
	if left == -1 {
		return -1
	}

	right := height(node.Right)
	if right == -1 {
		return -1
	}

	if left-right > 1 || right-left > 1 {
		return -1
	}

	if left > right {
		return left + 1
	}
	return right + 1
}

相似题目

题目	难度	考察点
110. 平衡二叉树	简单	递归
104. 二叉树的最大深度	简单	递归
543. 二叉树的直径	简单	递归
404. 左叶子之和	简单	DFS
剑指 Offer 55 - II. 平衡二叉树	简单	递归

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/51794850