企业官网建设流程全解析

🔥个人主页：北极的代码（欢迎来访）
🎬作者简介：java后端学习者
❄️个人专栏：苍穹外卖日记，SSM框架深入，JavaWeb
✨命运的结局尽可永在，不屈的挑战却不可须臾或缺！

前言：

大家好，我是代码不加冰，今天参加了学校的运动会，然后晚上还参加了一个三个小时的急救知识培训，所以今天的文章发的有点迟了，我们今天继续刷二叉树相关的题。

ps：关于急救的知识大家还是要了解的，生命第一，要少熬夜，希望大家都健健康康！

【摘要】

本文介绍了判断平衡二叉树的两种方法。平衡二叉树的定义要求每个节点的左右子树高度差不超过1，且左右子树也必须是平衡的。第一种自顶向下方法通过递归计算高度并判断平衡性，但存在重复计算问题，时间复杂度为O(n²)。推荐采用自底向上的后序遍历方法，在计算高度的同时判断平衡性，利用-1标记不平衡情况，时间复杂度优化为O(n)。文章通过示例详细说明了后序遍历的执行过程，并提供了完整的Java代码实现。

题目背景：110.平衡二叉树

给定一个二叉树，判断它是否是 平衡二叉树

示例 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

• 并且左右子树也分别是平衡二叉树

为什么要左右子树也分别平衡，我们看一个例子：

text

1 / \ 2 3 / \ 4 5 / \ 6 7

检查根节点1：

• 左子树高度 = 3（2→4→6）

• 右子树高度 = 3（3→5→7）

• 差值 = 0 ≤ 1 根节点平衡

但是！检查左子树（节点2）：

• 左子树高度 = 2（4→6）

• 右子树高度 = 0（null）

• 差值 = 2 > 1 左子树不平衡！

所以整棵树不平衡

核心思想

平衡二叉树的定义是递归的：

一棵树是平衡的 ⇔ 左子树平衡 && 右子树平衡 && |左高 - 右高| ≤ 1

因此，我们需要同时获取两个信息：

1. 当前树的高度

2. 当前树是否平衡

方案一：自顶向下（暴力法，不推荐）

java class Solution { public boolean isBalanced(TreeNode root) { if (root == null) return true; // 判断当前节点是否平衡 int leftHeight = getHeight(root.left); int rightHeight = getHeight(root.right); if (Math.abs(leftHeight - rightHeight) > 1) { return false; } // 递归判断左右子树 return isBalanced(root.left) && isBalanced(root.right); } // 计算树的高度 private int getHeight(TreeNode root) { if (root == null) return 0; return 1 + Math.max(getHeight(root.left), getHeight(root.right)); } }

问题：getHeight()会被重复调用，每个节点被访问多次，时间复杂度 O(n²)。

二、方案二：自底向上（推荐 ）

核心思想

后序遍历（左右根）：

1. 先递归计算左子树的高度和平衡性

2. 再递归计算右子树的高度和平衡性

3. 如果左右子树都平衡，且高度差 ≤ 1，则当前树平衡

4. 返回当前树的高度给上一层使用

巧妙之处：用特殊值（如 -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 getHeight(root) != -1; } // 返回树的高度，如果不平衡则返回 -1 private int getHeight(TreeNode root) { if (root == null) { return 0; } // 递归计算左子树高度 int leftHeight = getHeight(root.left); if (leftHeight == -1) { return -1; // 左子树不平衡，直接返回 -1 } // 递归计算右子树高度 int rightHeight = getHeight(root.right); if (rightHeight == -1) { return -1; // 右子树不平衡，直接返回 -1 } // 检查当前节点是否平衡 if (Math.abs(leftHeight - rightHeight) > 1) { return -1; // 当前节点不平衡 } // 返回当前树的高度 return 1 + Math.max(leftHeight, rightHeight); } }

关于：return getHeight(root) != -1的完整展开。

java public boolean isBalanced(TreeNode root) { int heightOrFlag = getHeight(root); // 得到 -1 或高度 if (heightOrFlag == -1) { return false; // 不平衡 } else { return true; // 平衡 } }

为什么每次都返回-1

1 / \ 2 3 / \ 4 5 / 6

• 节点6：正常 → 返回 1

• 节点4：左高=1，右高=0，差值=1 → 返回 2

• 节点5：正常 → 返回 1

• 节点2：左高=2，右高=1，差值=1 → 返回 3

• 节点3：正常 → 返回 1

• 节点1：左高=3，右高=1，差值=2 → 返回-1

一旦节点1返回 -1，整个递归结束，isBalanced收到 -1 →false

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

这行代码返回的是树的高度（一个正常值：0,1,2,3...）

然后在外层的isBalanced中：

java

public boolean isBalanced(TreeNode root) { return getHeight(root) != -1; }

• 如果getHeight(root)返回的是正常高度（0,1,2...）→!= -1是true→ 平衡

• 如果getHeight(root)返回的是-1→!= -1是false→ 不平衡

执行过程图解

以平衡树为例：

text

3 / \ 9 20 / \ 15 7

后序遍历的顺序是硬性规定：

text

对任意一棵树： 1. 后序遍历左子树 2. 后序遍历右子树 3. 访问根节点

不是“先左再根再右”，
也不是“哪边节点少先处理哪边”。

具体套到这棵树上

树结构：

3
/ \
9 20
/ \
15 7

第 1 步：从根节点 3 开始

规则：

• 先去左子树（9）

• 再去右子树（20）

• 最后访问 3

第 2 步：进入左子树 9

• 左空

• 右空

• 访问 9

此时输出：9

第 3 步：回到 3，进入右子树 20

规则（对 20 这棵树）：

• 先去左子树（15）

• 再去右子树（7）

• 最后访问 20

第 4 步：进入 15

• 左右空

• 访问 15

此时输出：9、15

第 5 步：回到 20，进入右子树 7

• 左右空

• 访问 7

此时输出：9、15、7

第 6 步：回到 20

• 左（15）已处理

• 右（7）已处理

• 访问 20

此时输出：9、15、7、20

第 7 步：回到 3

• 左（9）已处理

• 右（20）已处理

• 访问 3

最终输出：9、15、7、20、3

后序遍历过程：

步骤	节点	left高度	right高度	是否平衡	返回高度
1	9	0	0	✅	1
2	15	0	0	✅	1
3	7	0	0	✅	1
4	20	1	1	✅	2
5	3	1	2	✅	3

最终：没有返回 -1 → 平衡