百日算法修炼 · Day 15

百日算法修炼 · Day 15

主题：二叉树递归套路、树形 DP、完全二叉树、最近公共祖先、树上最大距离、员工快乐值 语言：Java　｜　建议用时：120～180 分钟

阅读方式

本文分为两个区域：

• 上半篇是独立练习区：只有题目、示例、思考问题和可折叠提示；
• 下半篇是参考答案区：包含优化后的代码、过程图解、递归信息设计、复杂度、易错点与验证思路。

建议先完成全部题目，再通过“查看参考答案”链接跳转。

Day 15 的主线不是背 8 道题，而是掌握一个可以反复迁移的套路：

向左子树要信息，向右子树要信息，再用左右信息加工出当前节点的信息。

这就是二叉树题里非常重要的 递归信息模型 / 树形 DP。

今日任务地图

#mermaid-svg-BSH5b8gIEQZHr2Ct{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-BSH5b8gIEQZHr2Ct .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-BSH5b8gIEQZHr2Ct .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-BSH5b8gIEQZHr2Ct .error-icon{fill:#552222;}#mermaid-svg-BSH5b8gIEQZHr2Ct .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-BSH5b8gIEQZHr2Ct .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-BSH5b8gIEQZHr2Ct .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-BSH5b8gIEQZHr2Ct .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-BSH5b8gIEQZHr2Ct .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-BSH5b8gIEQZHr2Ct .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-BSH5b8gIEQZHr2Ct .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-BSH5b8gIEQZHr2Ct .marker{fill:#333333;stroke:#333333;}#mermaid-svg-BSH5b8gIEQZHr2Ct .marker.cross{stroke:#333333;}#mermaid-svg-BSH5b8gIEQZHr2Ct svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-BSH5b8gIEQZHr2Ct p{margin:0;}#mermaid-svg-BSH5b8gIEQZHr2Ct .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-BSH5b8gIEQZHr2Ct .cluster-label text{fill:#333;}#mermaid-svg-BSH5b8gIEQZHr2Ct .cluster-label span{color:#333;}#mermaid-svg-BSH5b8gIEQZHr2Ct .cluster-label span p{background-color:transparent;}#mermaid-svg-BSH5b8gIEQZHr2Ct .label text,#mermaid-svg-BSH5b8gIEQZHr2Ct span{fill:#333;color:#333;}#mermaid-svg-BSH5b8gIEQZHr2Ct .node rect,#mermaid-svg-BSH5b8gIEQZHr2Ct .node circle,#mermaid-svg-BSH5b8gIEQZHr2Ct .node ellipse,#mermaid-svg-BSH5b8gIEQZHr2Ct .node polygon,#mermaid-svg-BSH5b8gIEQZHr2Ct .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-BSH5b8gIEQZHr2Ct .rough-node .label text,#mermaid-svg-BSH5b8gIEQZHr2Ct .node .label text,#mermaid-svg-BSH5b8gIEQZHr2Ct .image-shape .label,#mermaid-svg-BSH5b8gIEQZHr2Ct .icon-shape .label{text-anchor:middle;}#mermaid-svg-BSH5b8gIEQZHr2Ct .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-BSH5b8gIEQZHr2Ct .rough-node .label,#mermaid-svg-BSH5b8gIEQZHr2Ct .node .label,#mermaid-svg-BSH5b8gIEQZHr2Ct .image-shape .label,#mermaid-svg-BSH5b8gIEQZHr2Ct .icon-shape .label{text-align:center;}#mermaid-svg-BSH5b8gIEQZHr2Ct .node.clickable{cursor:pointer;}#mermaid-svg-BSH5b8gIEQZHr2Ct .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-BSH5b8gIEQZHr2Ct .arrowheadPath{fill:#333333;}#mermaid-svg-BSH5b8gIEQZHr2Ct .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-BSH5b8gIEQZHr2Ct .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-BSH5b8gIEQZHr2Ct .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-BSH5b8gIEQZHr2Ct .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-BSH5b8gIEQZHr2Ct .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-BSH5b8gIEQZHr2Ct .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-BSH5b8gIEQZHr2Ct .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-BSH5b8gIEQZHr2Ct .cluster text{fill:#333;}#mermaid-svg-BSH5b8gIEQZHr2Ct .cluster span{color:#333;}#mermaid-svg-BSH5b8gIEQZHr2Ct div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-BSH5b8gIEQZHr2Ct .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-BSH5b8gIEQZHr2Ct rect.text{fill:none;stroke-width:0;}#mermaid-svg-BSH5b8gIEQZHr2Ct .icon-shape,#mermaid-svg-BSH5b8gIEQZHr2Ct .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-BSH5b8gIEQZHr2Ct .icon-shape p,#mermaid-svg-BSH5b8gIEQZHr2Ct .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-BSH5b8gIEQZHr2Ct .icon-shape .label rect,#mermaid-svg-BSH5b8gIEQZHr2Ct .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-BSH5b8gIEQZHr2Ct .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-BSH5b8gIEQZHr2Ct .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-BSH5b8gIEQZHr2Ct :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

开始 Day 15

建立递归信息模型

平衡二叉树

满二叉树

二叉搜索树

最大搜索二叉子树

完全二叉树

最近公共祖先

树上最大距离

多叉树最大快乐值

统一复盘树形 DP

第一部分：独立练习区

先别急着翻答案。每道题开始前都问自己： “父节点为了做出判断，到底需要从左右子树拿到哪些信息？”

练习 1：判断平衡二叉树

给定一棵二叉树，判断它是否为平衡二叉树。

本文沿用本题代码约定：

root == null 时，对外返回 false

对于任意非空节点，平衡条件是：

1. 左子树平衡
2. 右子树平衡
3. 左右子树高度差不超过 1

思考问题

提示 1：父节点需要两个维度

父节点既要知道左右子树本身是否平衡，也要知道左右高度，才能判断当前节点的高度差。

提示 2：先相信子树已经解决

递归函数不需要关心左子树内部怎么判断，只要规定它能返回“是否平衡 + 高度”即可。

写完后再看：查看练习 1 参考答案

练习 2：判断满二叉树

这里先统一术语。

本文把“满二叉树”定义为通常所说的 Perfect Binary Tree（完美二叉树）：

每一层都被完全填满，所有叶子节点处于同一深度。

例如：

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

是满二叉树。

而下面这棵树虽然每个非叶子节点都有两个孩子，但叶子不在同一层，因此不是本文定义的满二叉树：

1
/ \\
2 3
/ \\
4 5

思考问题

提示：满不满不仅看结构，还看高度

左右子树都必须是满二叉树，并且高度必须完全相同。

写完后再看：查看练习 2 参考答案

练习 3：判断二叉搜索树

给定一棵二叉树，判断它是否为严格二叉搜索树。

本文采用严格定义：

左子树所有值 < 当前值 < 右子树所有值

因此不允许重复值跨越父节点边界。

思考问题

提示：不要只盯着直接孩子

左子树里最“大”的节点也必须小于当前节点；右子树里最“小”的节点也必须大于当前节点。

写完后再看：查看练习 3 参考答案

练习 4：最大搜索二叉子树的大小

给定一棵普通二叉树，返回其中节点数量最多的二叉搜索子树所包含的节点数。

例如：

6
/ \\
1 12
/ \\
10 13
/ \\
4 14

整棵树不一定是 BST，但某个局部子树可能是 BST。

思考问题

提示 1：有两类答案来源

最大 BST 要么完全位于左子树，要么完全位于右子树，要么就是“以当前节点为根的整棵子树”。

提示 2：整棵成立时要算整棵大小

如果当前子树本身是 BST，答案不是“孩子答案 + 1”，而是当前整棵子树的节点总数。

写完后再看：查看练习 4 参考答案

练习 5：判断完全二叉树

完全二叉树（Complete Binary Tree）的直观规则：

除最后一层外，其余层必须填满；最后一层的节点必须从左向右连续出现。

例如：

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

是完全二叉树。

而：

1
/ \\
2 3
\\
5

不是，因为出现了“有右孩子但没有左孩子”。

要求分别思考：

• 方法一：层序遍历
• 方法二：递归信息模型

思考问题

提示 1：层序遍历维护 leafMode

一旦某个节点缺少任意一个孩子，之后层序遍历到的所有节点都必须没有孩子。

提示 2：递归时分类讨论高度

完全二叉树只可能出现“左右等高”或“左边恰好高 1”两大高度关系，再结合满二叉树状态判断。

写完后再看：查看练习 5 参考答案

练习 6：最近公共祖先

给定二叉树中的两个节点 first 和 second，返回它们的最近公共祖先（Lowest Common Ancestor, LCA）。

例如：

1
/ \\
2 3
/ \\
4 5

节点 4 和 5 的最近公共祖先是 2。

节点 2 和 5 的最近公共祖先是 2 本身。

思考问题

提示：Info 可以描述三件事

当前子树是否包含 first、是否包含 second、当前子树中是否已经确定最近公共祖先。

写完后再看：查看练习 6 参考答案

练习 7：二叉树中的最大距离

给定一棵二叉树，返回任意两个节点之间路径的最大长度。

为了避免歧义，本文统一定义：

距离按路径上经过的节点数计算。

因此单个节点的最大距离是：

1

例如：

1
/ \\
2 3
/
4

最长路径可以是：

4 -> 2 -> 1 -> 3

经过 4 个节点，所以答案是 4。

思考问题

提示：答案只有三种来源

左子树内部、右子树内部、从左边最深处经过当前节点走到右边最深处。

写完后再看：查看练习 7 参考答案

练习 8：派对的最大快乐值

公司的组织结构是一棵没有环的多叉树：

• 老板是根节点；
• 每个员工有唯一直接上级；
• 每个员工有一个快乐值；
• 如果某员工参加派对，那么他的所有直接下级都不能参加；
• 目标是让总快乐值最大。

思考问题

如果当前员工是 x：

提示 1：当前员工来

当前员工来的情况下，每个直接下级都必须不来，所以只能累加下级的 no。

提示 2：当前员工不来

当前员工不来时，每个下级可以在“来”和“不来”中选择快乐值更大的方案。

写完后再看：查看练习 8 参考答案

第二部分：参考答案与图解

到这里再对照答案。 比代码更重要的是检查：你为每道题设计的 Info，是否恰好包含父节点真正需要的信息？

答案 1：判断平衡二叉树

返回练习 1

问题回顾

当前节点要判断自己平衡，需要：

左子树：是否平衡 + 高度
右子树：是否平衡 + 高度

于是当前节点可以得到：

isBalanced
=
left.isBalanced
&& right.isBalanced
&& abs(left.height – right.height) <= 1

同时：

height = max(left.height, right.height) + 1

信息流

#mermaid-svg-u1PNUbupYwHCIbn6{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-u1PNUbupYwHCIbn6 .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-u1PNUbupYwHCIbn6 .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-u1PNUbupYwHCIbn6 .error-icon{fill:#552222;}#mermaid-svg-u1PNUbupYwHCIbn6 .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-u1PNUbupYwHCIbn6 .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-u1PNUbupYwHCIbn6 .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-u1PNUbupYwHCIbn6 .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-u1PNUbupYwHCIbn6 .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-u1PNUbupYwHCIbn6 .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-u1PNUbupYwHCIbn6 .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-u1PNUbupYwHCIbn6 .marker{fill:#333333;stroke:#333333;}#mermaid-svg-u1PNUbupYwHCIbn6 .marker.cross{stroke:#333333;}#mermaid-svg-u1PNUbupYwHCIbn6 svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-u1PNUbupYwHCIbn6 p{margin:0;}#mermaid-svg-u1PNUbupYwHCIbn6 .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-u1PNUbupYwHCIbn6 .cluster-label text{fill:#333;}#mermaid-svg-u1PNUbupYwHCIbn6 .cluster-label span{color:#333;}#mermaid-svg-u1PNUbupYwHCIbn6 .cluster-label span p{background-color:transparent;}#mermaid-svg-u1PNUbupYwHCIbn6 .label text,#mermaid-svg-u1PNUbupYwHCIbn6 span{fill:#333;color:#333;}#mermaid-svg-u1PNUbupYwHCIbn6 .node rect,#mermaid-svg-u1PNUbupYwHCIbn6 .node circle,#mermaid-svg-u1PNUbupYwHCIbn6 .node ellipse,#mermaid-svg-u1PNUbupYwHCIbn6 .node polygon,#mermaid-svg-u1PNUbupYwHCIbn6 .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-u1PNUbupYwHCIbn6 .rough-node .label text,#mermaid-svg-u1PNUbupYwHCIbn6 .node .label text,#mermaid-svg-u1PNUbupYwHCIbn6 .image-shape .label,#mermaid-svg-u1PNUbupYwHCIbn6 .icon-shape .label{text-anchor:middle;}#mermaid-svg-u1PNUbupYwHCIbn6 .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-u1PNUbupYwHCIbn6 .rough-node .label,#mermaid-svg-u1PNUbupYwHCIbn6 .node .label,#mermaid-svg-u1PNUbupYwHCIbn6 .image-shape .label,#mermaid-svg-u1PNUbupYwHCIbn6 .icon-shape .label{text-align:center;}#mermaid-svg-u1PNUbupYwHCIbn6 .node.clickable{cursor:pointer;}#mermaid-svg-u1PNUbupYwHCIbn6 .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-u1PNUbupYwHCIbn6 .arrowheadPath{fill:#333333;}#mermaid-svg-u1PNUbupYwHCIbn6 .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-u1PNUbupYwHCIbn6 .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-u1PNUbupYwHCIbn6 .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-u1PNUbupYwHCIbn6 .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-u1PNUbupYwHCIbn6 .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-u1PNUbupYwHCIbn6 .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-u1PNUbupYwHCIbn6 .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-u1PNUbupYwHCIbn6 .cluster text{fill:#333;}#mermaid-svg-u1PNUbupYwHCIbn6 .cluster span{color:#333;}#mermaid-svg-u1PNUbupYwHCIbn6 div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-u1PNUbupYwHCIbn6 .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-u1PNUbupYwHCIbn6 rect.text{fill:none;stroke-width:0;}#mermaid-svg-u1PNUbupYwHCIbn6 .icon-shape,#mermaid-svg-u1PNUbupYwHCIbn6 .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-u1PNUbupYwHCIbn6 .icon-shape p,#mermaid-svg-u1PNUbupYwHCIbn6 .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-u1PNUbupYwHCIbn6 .icon-shape .label rect,#mermaid-svg-u1PNUbupYwHCIbn6 .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-u1PNUbupYwHCIbn6 .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-u1PNUbupYwHCIbn6 .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-u1PNUbupYwHCIbn6 :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

左子树 InfoisBalanced + height

当前节点

右子树 InfoisBalanced + height

计算当前 height

计算当前 isBalanced

向父节点返回 Info

完整代码

package class07;

import utils.TreeNode;

/**
* 判断二叉树是否为平衡二叉树。
*
* 本题沿用约定：
* 对外接口中 root == null 时返回 false。
*/
public class Code01_IsBalanced {

/**
* 每棵子树向父节点汇报两项信息：
* 1. 自己是否平衡；
* 2. 自己的高度。
*/
private static class Info {
final boolean balanced;
final int height;

Info(boolean balanced, int height) {
this.balanced = balanced;
this.height = height;
}
}

public static boolean isBalanced(TreeNode root) {
if (root == null) {
return false;
}
return process(root).balanced;
}

/**
* 返回“以 root 为根的子树”的完整信息。
*/
private static Info process(TreeNode root) {
// 空树在递归内部视为平衡，高度为 0，
// 这样父节点可以直接统一处理，不必反复判空。
if (root == null) {
return new Info(true, 0);
}

Info left = process(root.left);
Info right = process(root.right);

int height = Math.max(left.height, right.height) + 1;

boolean balanced =
left.balanced
&& right.balanced
&& Math.abs(left.height – right.height) <= 1;

return new Info(balanced, height);
}
}

为什么空树在递归内部返回 true？

因为空树不会破坏父节点的平衡性。

如果一个叶子节点：

left -> (true, 0)
right -> (true, 0)

那么：

height = 1
高度差 = 0

自然得到叶子节点平衡。

复杂度

其中 H 为树高。

易错点

• 只返回高度，不返回子树自身是否平衡；
• 只检查当前高度差，却漏掉某个子树内部已经不平衡；
• 混淆“对外空树约定”和“递归内部空树基线”。

答案 2：判断满二叉树

返回练习 2

问题回顾

本文把满二叉树定义为 Perfect Binary Tree。

当前节点要成为满二叉树，必须同时满足：

左子树是满二叉树
右子树是满二叉树
左高度 == 右高度

递归图

#mermaid-svg-JZ2IXrmZt48e4gfj{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-JZ2IXrmZt48e4gfj .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-JZ2IXrmZt48e4gfj .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-JZ2IXrmZt48e4gfj .error-icon{fill:#552222;}#mermaid-svg-JZ2IXrmZt48e4gfj .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-JZ2IXrmZt48e4gfj .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-JZ2IXrmZt48e4gfj .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-JZ2IXrmZt48e4gfj .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-JZ2IXrmZt48e4gfj .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-JZ2IXrmZt48e4gfj .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-JZ2IXrmZt48e4gfj .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-JZ2IXrmZt48e4gfj .marker{fill:#333333;stroke:#333333;}#mermaid-svg-JZ2IXrmZt48e4gfj .marker.cross{stroke:#333333;}#mermaid-svg-JZ2IXrmZt48e4gfj svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-JZ2IXrmZt48e4gfj p{margin:0;}#mermaid-svg-JZ2IXrmZt48e4gfj .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-JZ2IXrmZt48e4gfj .cluster-label text{fill:#333;}#mermaid-svg-JZ2IXrmZt48e4gfj .cluster-label span{color:#333;}#mermaid-svg-JZ2IXrmZt48e4gfj .cluster-label span p{background-color:transparent;}#mermaid-svg-JZ2IXrmZt48e4gfj .label text,#mermaid-svg-JZ2IXrmZt48e4gfj span{fill:#333;color:#333;}#mermaid-svg-JZ2IXrmZt48e4gfj .node rect,#mermaid-svg-JZ2IXrmZt48e4gfj .node circle,#mermaid-svg-JZ2IXrmZt48e4gfj .node ellipse,#mermaid-svg-JZ2IXrmZt48e4gfj .node polygon,#mermaid-svg-JZ2IXrmZt48e4gfj .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-JZ2IXrmZt48e4gfj .rough-node .label text,#mermaid-svg-JZ2IXrmZt48e4gfj .node .label text,#mermaid-svg-JZ2IXrmZt48e4gfj .image-shape .label,#mermaid-svg-JZ2IXrmZt48e4gfj .icon-shape .label{text-anchor:middle;}#mermaid-svg-JZ2IXrmZt48e4gfj .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-JZ2IXrmZt48e4gfj .rough-node .label,#mermaid-svg-JZ2IXrmZt48e4gfj .node .label,#mermaid-svg-JZ2IXrmZt48e4gfj .image-shape .label,#mermaid-svg-JZ2IXrmZt48e4gfj .icon-shape .label{text-align:center;}#mermaid-svg-JZ2IXrmZt48e4gfj .node.clickable{cursor:pointer;}#mermaid-svg-JZ2IXrmZt48e4gfj .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-JZ2IXrmZt48e4gfj .arrowheadPath{fill:#333333;}#mermaid-svg-JZ2IXrmZt48e4gfj .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-JZ2IXrmZt48e4gfj .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-JZ2IXrmZt48e4gfj .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-JZ2IXrmZt48e4gfj .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-JZ2IXrmZt48e4gfj .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-JZ2IXrmZt48e4gfj .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-JZ2IXrmZt48e4gfj .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-JZ2IXrmZt48e4gfj .cluster text{fill:#333;}#mermaid-svg-JZ2IXrmZt48e4gfj .cluster span{color:#333;}#mermaid-svg-JZ2IXrmZt48e4gfj div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-JZ2IXrmZt48e4gfj .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-JZ2IXrmZt48e4gfj rect.text{fill:none;stroke-width:0;}#mermaid-svg-JZ2IXrmZt48e4gfj .icon-shape,#mermaid-svg-JZ2IXrmZt48e4gfj .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-JZ2IXrmZt48e4gfj .icon-shape p,#mermaid-svg-JZ2IXrmZt48e4gfj .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-JZ2IXrmZt48e4gfj .icon-shape .label rect,#mermaid-svg-JZ2IXrmZt48e4gfj .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-JZ2IXrmZt48e4gfj .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-JZ2IXrmZt48e4gfj .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-JZ2IXrmZt48e4gfj :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

否

是

是

否

获取左 Info

左右都是 full?

获取右 Info

当前不是满二叉树

左右高度相同?

当前是满二叉树

完整代码

package class07;

import utils.TreeNode;

/**
* 判断是否为满二叉树（Perfect Binary Tree）。
*
* 本题沿用约定：
* 对外接口中 root == null 时返回 false。
*/
public class Code02_IsFull {

private static class Info {
final boolean full;
final int height;

Info(boolean full, int height) {
this.full = full;
this.height = height;
}
}

public static boolean isFull(TreeNode root) {
if (root == null) {
return false;
}
return process(root).full;
}

private static Info process(TreeNode root) {
if (root == null) {
return new Info(true, 0);
}

Info left = process(root.left);
Info right = process(root.right);

int height = Math.max(left.height, right.height) + 1;

boolean full =
left.full
&& right.full
&& left.height == right.height;

return new Info(full, height);
}
}

另一种常见判法

如果一棵满二叉树高度为 h，节点数满足：

nodes = 2^h – 1

因此也可以递归统计：

height
nodes

最终检查：

nodes == 2^height – 1

但直接维护 isFull + height 更贴合今天的“递归信息模型”。

复杂度

易错点

• 把“Full Binary Tree（每个节点 0 或 2 个孩子）”和“Perfect Binary Tree（每层填满）”混在一起；
• 只看左右是否都有孩子，却不比较子树高度；
• 只比较高度，不检查左右子树自身是否已经违反条件。

答案 3：判断二叉搜索树

返回练习 3

问题回顾

当前节点成为 BST，需要：

左子树本身是 BST
右子树本身是 BST
左子树最大值 < root.value
root.value < 右子树最小值

因此每棵子树至少要返回：

isBST
min
max

为什么不能只比较直接孩子？

下面这棵树：

10
/ \\
5 15
/
6

如果只比较：

5 < 10 < 15

似乎没有问题。

但 6 位于 10 的右子树，却小于 10，所以整棵树不是 BST。

信息合并

#mermaid-svg-z3gxeio7SctnB3PR{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-z3gxeio7SctnB3PR .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-z3gxeio7SctnB3PR .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-z3gxeio7SctnB3PR .error-icon{fill:#552222;}#mermaid-svg-z3gxeio7SctnB3PR .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-z3gxeio7SctnB3PR .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-z3gxeio7SctnB3PR .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-z3gxeio7SctnB3PR .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-z3gxeio7SctnB3PR .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-z3gxeio7SctnB3PR .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-z3gxeio7SctnB3PR .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-z3gxeio7SctnB3PR .marker{fill:#333333;stroke:#333333;}#mermaid-svg-z3gxeio7SctnB3PR .marker.cross{stroke:#333333;}#mermaid-svg-z3gxeio7SctnB3PR svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-z3gxeio7SctnB3PR p{margin:0;}#mermaid-svg-z3gxeio7SctnB3PR .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-z3gxeio7SctnB3PR .cluster-label text{fill:#333;}#mermaid-svg-z3gxeio7SctnB3PR .cluster-label span{color:#333;}#mermaid-svg-z3gxeio7SctnB3PR .cluster-label span p{background-color:transparent;}#mermaid-svg-z3gxeio7SctnB3PR .label text,#mermaid-svg-z3gxeio7SctnB3PR span{fill:#333;color:#333;}#mermaid-svg-z3gxeio7SctnB3PR .node rect,#mermaid-svg-z3gxeio7SctnB3PR .node circle,#mermaid-svg-z3gxeio7SctnB3PR .node ellipse,#mermaid-svg-z3gxeio7SctnB3PR .node polygon,#mermaid-svg-z3gxeio7SctnB3PR .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-z3gxeio7SctnB3PR .rough-node .label text,#mermaid-svg-z3gxeio7SctnB3PR .node .label text,#mermaid-svg-z3gxeio7SctnB3PR .image-shape .label,#mermaid-svg-z3gxeio7SctnB3PR .icon-shape .label{text-anchor:middle;}#mermaid-svg-z3gxeio7SctnB3PR .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-z3gxeio7SctnB3PR .rough-node .label,#mermaid-svg-z3gxeio7SctnB3PR .node .label,#mermaid-svg-z3gxeio7SctnB3PR .image-shape .label,#mermaid-svg-z3gxeio7SctnB3PR .icon-shape .label{text-align:center;}#mermaid-svg-z3gxeio7SctnB3PR .node.clickable{cursor:pointer;}#mermaid-svg-z3gxeio7SctnB3PR .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-z3gxeio7SctnB3PR .arrowheadPath{fill:#333333;}#mermaid-svg-z3gxeio7SctnB3PR .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-z3gxeio7SctnB3PR .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-z3gxeio7SctnB3PR .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-z3gxeio7SctnB3PR .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-z3gxeio7SctnB3PR .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-z3gxeio7SctnB3PR .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-z3gxeio7SctnB3PR .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-z3gxeio7SctnB3PR .cluster text{fill:#333;}#mermaid-svg-z3gxeio7SctnB3PR .cluster span{color:#333;}#mermaid-svg-z3gxeio7SctnB3PR div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-z3gxeio7SctnB3PR .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-z3gxeio7SctnB3PR rect.text{fill:none;stroke-width:0;}#mermaid-svg-z3gxeio7SctnB3PR .icon-shape,#mermaid-svg-z3gxeio7SctnB3PR .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-z3gxeio7SctnB3PR .icon-shape p,#mermaid-svg-z3gxeio7SctnB3PR .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-z3gxeio7SctnB3PR .icon-shape .label rect,#mermaid-svg-z3gxeio7SctnB3PR .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-z3gxeio7SctnB3PR .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-z3gxeio7SctnB3PR .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-z3gxeio7SctnB3PR :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

左子树isBST min max

当前节点

右子树isBST min max

计算当前 min / max

检查 left.max < value

检查 value < right.min

返回当前 Info

完整代码

package class07;

import utils.TreeNode;

/**
* 判断是否为严格二叉搜索树。
*
* 严格定义：
* 左子树所有值 < 当前值 < 右子树所有值。
*/
public class Code03_IsBST {

private static class Info {
final boolean bst;
final int min;
final int max;

Info(boolean bst, int min, int max) {
this.bst = bst;
this.min = min;
this.max = max;
}
}

public static boolean isBST(TreeNode root) {
if (root == null) {
return false;
}
return process(root).bst;
}

private static Info process(TreeNode root) {
if (root == null) {
return null;
}

Info left = process(root.left);
Info right = process(root.right);

int min = root.value;
int max = root.value;

if (left != null) {
min = Math.min(min, left.min);
max = Math.max(max, left.max);
}

if (right != null) {
min = Math.min(min, right.min);
max = Math.max(max, right.max);
}

boolean leftValid =
left == null
|| (left.bst && left.max < root.value);

boolean rightValid =
right == null
|| (right.bst && root.value < right.min);

return new Info(leftValid && rightValid, min, max);
}
}

这里的关键不是 min / max，而是“全局约束”

BST 的约束不是：

父亲只管直接孩子

而是：

父亲必须压住整棵左子树的最大值
父亲必须小于整棵右子树的最小值

这也是为什么递归信息要向上汇总“极值”。

复杂度

易错点

• 只比较左右孩子；
• 忘记检查左右子树自身是否为 BST；
• 严格 BST 与允许重复值的 BST 规则混用；
• min / max 更新漏掉当前节点自身。

答案 4：最大搜索二叉子树的大小

返回练习 4

问题回顾

这道题比“判断 BST”多了一层：

不仅要知道当前子树是不是 BST，还要知道当前范围内最大的 BST 有多大。

所以每棵子树可以返回：

isBST
min
max
size
maxSubBSTSize

其中：

• size：当前子树总节点数；
• maxSubBSTSize：当前子树范围内最大的 BST 节点数。

三种答案来源

#mermaid-svg-UeDAGvAEvJe9t89f{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-UeDAGvAEvJe9t89f .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-UeDAGvAEvJe9t89f .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-UeDAGvAEvJe9t89f .error-icon{fill:#552222;}#mermaid-svg-UeDAGvAEvJe9t89f .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-UeDAGvAEvJe9t89f .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-UeDAGvAEvJe9t89f .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-UeDAGvAEvJe9t89f .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-UeDAGvAEvJe9t89f .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-UeDAGvAEvJe9t89f .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-UeDAGvAEvJe9t89f .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-UeDAGvAEvJe9t89f .marker{fill:#333333;stroke:#333333;}#mermaid-svg-UeDAGvAEvJe9t89f .marker.cross{stroke:#333333;}#mermaid-svg-UeDAGvAEvJe9t89f svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-UeDAGvAEvJe9t89f p{margin:0;}#mermaid-svg-UeDAGvAEvJe9t89f .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-UeDAGvAEvJe9t89f .cluster-label text{fill:#333;}#mermaid-svg-UeDAGvAEvJe9t89f .cluster-label span{color:#333;}#mermaid-svg-UeDAGvAEvJe9t89f .cluster-label span p{background-color:transparent;}#mermaid-svg-UeDAGvAEvJe9t89f .label text,#mermaid-svg-UeDAGvAEvJe9t89f span{fill:#333;color:#333;}#mermaid-svg-UeDAGvAEvJe9t89f .node rect,#mermaid-svg-UeDAGvAEvJe9t89f .node circle,#mermaid-svg-UeDAGvAEvJe9t89f .node ellipse,#mermaid-svg-UeDAGvAEvJe9t89f .node polygon,#mermaid-svg-UeDAGvAEvJe9t89f .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-UeDAGvAEvJe9t89f .rough-node .label text,#mermaid-svg-UeDAGvAEvJe9t89f .node .label text,#mermaid-svg-UeDAGvAEvJe9t89f .image-shape .label,#mermaid-svg-UeDAGvAEvJe9t89f .icon-shape .label{text-anchor:middle;}#mermaid-svg-UeDAGvAEvJe9t89f .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-UeDAGvAEvJe9t89f .rough-node .label,#mermaid-svg-UeDAGvAEvJe9t89f .node .label,#mermaid-svg-UeDAGvAEvJe9t89f .image-shape .label,#mermaid-svg-UeDAGvAEvJe9t89f .icon-shape .label{text-align:center;}#mermaid-svg-UeDAGvAEvJe9t89f .node.clickable{cursor:pointer;}#mermaid-svg-UeDAGvAEvJe9t89f .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-UeDAGvAEvJe9t89f .arrowheadPath{fill:#333333;}#mermaid-svg-UeDAGvAEvJe9t89f .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-UeDAGvAEvJe9t89f .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-UeDAGvAEvJe9t89f .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-UeDAGvAEvJe9t89f .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-UeDAGvAEvJe9t89f .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-UeDAGvAEvJe9t89f .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-UeDAGvAEvJe9t89f .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-UeDAGvAEvJe9t89f .cluster text{fill:#333;}#mermaid-svg-UeDAGvAEvJe9t89f .cluster span{color:#333;}#mermaid-svg-UeDAGvAEvJe9t89f div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-UeDAGvAEvJe9t89f .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-UeDAGvAEvJe9t89f rect.text{fill:none;stroke-width:0;}#mermaid-svg-UeDAGvAEvJe9t89f .icon-shape,#mermaid-svg-UeDAGvAEvJe9t89f .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-UeDAGvAEvJe9t89f .icon-shape p,#mermaid-svg-UeDAGvAEvJe9t89f .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-UeDAGvAEvJe9t89f .icon-shape .label rect,#mermaid-svg-UeDAGvAEvJe9t89f .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-UeDAGvAEvJe9t89f .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-UeDAGvAEvJe9t89f .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-UeDAGvAEvJe9t89f :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

当前子树的最大 BST

完全在左子树

完全在右子树

就是当前整棵子树

完整代码

package class07;

import utils.TreeNode;

/**
* 返回二叉树中最大二叉搜索子树的节点数。
*/
public class Code04_MaxSubBSTSize {

private static class Info {
final boolean bst;
final int min;
final int max;

// 以当前节点为根的整棵子树节点数。
final int size;

// 当前子树范围内，最大 BST 的节点数。
final int maxSubBSTSize;

Info(boolean bst, int min, int max, int size, int maxSubBSTSize) {
this.bst = bst;
this.min = min;
this.max = max;
this.size = size;
this.maxSubBSTSize = maxSubBSTSize;
}
}

public static int maxSubBSTSize(TreeNode root) {
if (root == null) {
return 0;
}
return process(root).maxSubBSTSize;
}

private static Info process(TreeNode root) {
if (root == null) {
return null;
}

Info left = process(root.left);
Info right = process(root.right);

int size = 1;
int min = root.value;
int max = root.value;

if (left != null) {
size += left.size;
min = Math.min(min, left.min);
max = Math.max(max, left.max);
}

if (right != null) {
size += right.size;
min = Math.min(min, right.min);
max = Math.max(max, right.max);
}

boolean leftValid =
left == null
|| (left.bst && left.max < root.value);

boolean rightValid =
right == null
|| (right.bst && root.value < right.min);

boolean bst = leftValid && rightValid;

int leftBest = left == null ? 0 : left.maxSubBSTSize;
int rightBest = right == null ? 0 : right.maxSubBSTSize;

int maxSubBSTSize;

if (bst) {
// 当前整棵子树就是 BST，
// 最大 BST 的大小就是当前子树的总节点数。
maxSubBSTSize = size;
} else {
// 当前整棵不是 BST，
// 最优答案只能来自左右子树。
maxSubBSTSize = Math.max(leftBest, rightBest);
}

return new Info(bst, min, max, size, maxSubBSTSize);
}
}

为什么需要 size？

假设：

左子树总大小 = 7
左子树最大 BST = 3

右子树总大小 = 5
右子树最大 BST = 2

如果当前整棵最终被证明是 BST，那么左右子树实际上也必须整体是 BST。

因此真正需要的是：

7 + 5 + 1 = 13

而不能写：

max(3, 2) + 1 = 4

复杂度

易错点

• 把“子树总大小”和“子树内部最大 BST 大小”混为一谈；
• 当前整棵是 BST 时只执行 best + 1；
• 判断 BST 时忘记左右子树本身也必须是 BST；
• 极值信息没有继续向父节点传递。

答案 5：判断完全二叉树

返回练习 5

方法一：层序遍历

核心规则

层序遍历时有两个直接判错规则：

规则 1：
有右孩子，但没有左孩子 -> false

以及：

规则 2：
一旦遇到“孩子不双全”的节点，
后面所有节点都必须是叶子节点

状态图

#mermaid-svg-Wj4LlSBDWJ1RNlw1{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-Wj4LlSBDWJ1RNlw1 .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-Wj4LlSBDWJ1RNlw1 .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-Wj4LlSBDWJ1RNlw1 .error-icon{fill:#552222;}#mermaid-svg-Wj4LlSBDWJ1RNlw1 .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-Wj4LlSBDWJ1RNlw1 .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-Wj4LlSBDWJ1RNlw1 .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-Wj4LlSBDWJ1RNlw1 .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-Wj4LlSBDWJ1RNlw1 .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-Wj4LlSBDWJ1RNlw1 .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-Wj4LlSBDWJ1RNlw1 .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-Wj4LlSBDWJ1RNlw1 .marker{fill:#333333;stroke:#333333;}#mermaid-svg-Wj4LlSBDWJ1RNlw1 .marker.cross{stroke:#333333;}#mermaid-svg-Wj4LlSBDWJ1RNlw1 svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-Wj4LlSBDWJ1RNlw1 p{margin:0;}#mermaid-svg-Wj4LlSBDWJ1RNlw1 .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-Wj4LlSBDWJ1RNlw1 .cluster-label text{fill:#333;}#mermaid-svg-Wj4LlSBDWJ1RNlw1 .cluster-label span{color:#333;}#mermaid-svg-Wj4LlSBDWJ1RNlw1 .cluster-label span p{background-color:transparent;}#mermaid-svg-Wj4LlSBDWJ1RNlw1 .label text,#mermaid-svg-Wj4LlSBDWJ1RNlw1 span{fill:#333;color:#333;}#mermaid-svg-Wj4LlSBDWJ1RNlw1 .node rect,#mermaid-svg-Wj4LlSBDWJ1RNlw1 .node circle,#mermaid-svg-Wj4LlSBDWJ1RNlw1 .node ellipse,#mermaid-svg-Wj4LlSBDWJ1RNlw1 .node polygon,#mermaid-svg-Wj4LlSBDWJ1RNlw1 .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-Wj4LlSBDWJ1RNlw1 .rough-node .label text,#mermaid-svg-Wj4LlSBDWJ1RNlw1 .node .label text,#mermaid-svg-Wj4LlSBDWJ1RNlw1 .image-shape .label,#mermaid-svg-Wj4LlSBDWJ1RNlw1 .icon-shape .label{text-anchor:middle;}#mermaid-svg-Wj4LlSBDWJ1RNlw1 .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-Wj4LlSBDWJ1RNlw1 .rough-node .label,#mermaid-svg-Wj4LlSBDWJ1RNlw1 .node .label,#mermaid-svg-Wj4LlSBDWJ1RNlw1 .image-shape .label,#mermaid-svg-Wj4LlSBDWJ1RNlw1 .icon-shape .label{text-align:center;}#mermaid-svg-Wj4LlSBDWJ1RNlw1 .node.clickable{cursor:pointer;}#mermaid-svg-Wj4LlSBDWJ1RNlw1 .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-Wj4LlSBDWJ1RNlw1 .arrowheadPath{fill:#333333;}#mermaid-svg-Wj4LlSBDWJ1RNlw1 .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-Wj4LlSBDWJ1RNlw1 .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-Wj4LlSBDWJ1RNlw1 .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-Wj4LlSBDWJ1RNlw1 .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-Wj4LlSBDWJ1RNlw1 .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-Wj4LlSBDWJ1RNlw1 .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-Wj4LlSBDWJ1RNlw1 .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-Wj4LlSBDWJ1RNlw1 .cluster text{fill:#333;}#mermaid-svg-Wj4LlSBDWJ1RNlw1 .cluster span{color:#333;}#mermaid-svg-Wj4LlSBDWJ1RNlw1 div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-Wj4LlSBDWJ1RNlw1 .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-Wj4LlSBDWJ1RNlw1 rect.text{fill:none;stroke-width:0;}#mermaid-svg-Wj4LlSBDWJ1RNlw1 .icon-shape,#mermaid-svg-Wj4LlSBDWJ1RNlw1 .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-Wj4LlSBDWJ1RNlw1 .icon-shape p,#mermaid-svg-Wj4LlSBDWJ1RNlw1 .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-Wj4LlSBDWJ1RNlw1 .icon-shape .label rect,#mermaid-svg-Wj4LlSBDWJ1RNlw1 .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-Wj4LlSBDWJ1RNlw1 .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-Wj4LlSBDWJ1RNlw1 .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-Wj4LlSBDWJ1RNlw1 :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

是

否

是

否

是

否

层序取出当前节点

无左但有右?

返回 false

已进入 leafMode 且当前还有孩子?

非空孩子入队

当前缺少任意孩子?

leafMode = true

继续

完整代码

package class07;

import utils.TreeNode;

import java.util.ArrayDeque;
import java.util.Queue;

/**
* 判断完全二叉树。
*/
public class Code05_IsCBT {

/**
* 本题沿用约定：
* root == null 时对外返回 false。
*/
public static boolean isCBT(TreeNode root) {
if (root == null) {
return false;
}
return bfs(root);
}

private static boolean bfs(TreeNode root) {
Queue<TreeNode> queue = new ArrayDeque<>();
queue.offer(root);

// 一旦进入 leafMode，
// 后面遍历到的节点都必须是叶子。
boolean leafMode = false;

while (!queue.isEmpty()) {
TreeNode cur = queue.poll();
TreeNode left = cur.left;
TreeNode right = cur.right;

// 有右无左，直接违反完全二叉树定义。
if (left == null && right != null) {
return false;
}

// 已经进入“后续必须是叶子”的阶段，
// 当前却仍然有孩子。
if (leafMode && (left != null || right != null)) {
return false;
}

if (left != null) {
queue.offer(left);
}

if (right != null) {
queue.offer(right);
}

// 只要孩子不双全，从下一个节点开始必须全是叶子。
if (left == null || right == null) {
leafMode = true;
}
}

return true;
}
}

方法二：递归信息模型

每棵子树向上返回：

isFull
isCBT
height

完全二叉树的递归组合

可以压缩成：

情况 A：
左满，右 CBT，左右等高

情况 B：
左 CBT，右满，左比右高 1

因为满二叉树本身也一定是完全二叉树，所以这两条可以覆盖标准组合。

递归版代码

private static class Info {
final boolean full;
final boolean cbt;
final int height;

Info(boolean full, boolean cbt, int height) {
this.full = full;
this.cbt = cbt;
this.height = height;
}
}

private static Info process(TreeNode root) {
if (root == null) {
return new Info(true, true, 0);
}

Info left = process(root.left);
Info right = process(root.right);

int height = Math.max(left.height, right.height) + 1;

boolean full =
left.full
&& right.full
&& left.height == right.height;

boolean cbt =
// 左右等高：
// 左边必须满，右边可以是完全二叉树。
(left.full
&& right.cbt
&& left.height == right.height)

||

// 左边恰好高 1：
// 左边可以是完全二叉树，右边必须满。
(left.cbt
&& right.full
&& left.height == right.height + 1);

return new Info(full, cbt, height);
}

如果要对外使用：

public static boolean isCBTByRecursion(TreeNode root) {
return root != null && process(root).cbt;
}

两种方法怎么选？

复杂度

两种方法都是：

W 是树的最大宽度。

易错点

• 往 ArrayDeque 中加入 null；
• 只检查“有右无左”，漏掉进入 leafMode 后还有孩子；
• 递归法只返回 isCBT，导致父节点无法判断组合情况；
• 把满二叉树与完全二叉树概念混淆。

答案 6：最近公共祖先

返回练习 6

问题回顾

每棵子树返回：

foundFirst
foundSecond
ancestor

含义分别是：

• 当前子树里是否找到 first；
• 当前子树里是否找到 second；
• 当前子树里是否已经确定最终最近公共祖先。

递归过程

#mermaid-svg-rzX01PkbysltPhMj{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-rzX01PkbysltPhMj .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-rzX01PkbysltPhMj .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-rzX01PkbysltPhMj .error-icon{fill:#552222;}#mermaid-svg-rzX01PkbysltPhMj .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-rzX01PkbysltPhMj .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-rzX01PkbysltPhMj .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-rzX01PkbysltPhMj .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-rzX01PkbysltPhMj .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-rzX01PkbysltPhMj .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-rzX01PkbysltPhMj .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-rzX01PkbysltPhMj .marker{fill:#333333;stroke:#333333;}#mermaid-svg-rzX01PkbysltPhMj .marker.cross{stroke:#333333;}#mermaid-svg-rzX01PkbysltPhMj svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-rzX01PkbysltPhMj p{margin:0;}#mermaid-svg-rzX01PkbysltPhMj .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-rzX01PkbysltPhMj .cluster-label text{fill:#333;}#mermaid-svg-rzX01PkbysltPhMj .cluster-label span{color:#333;}#mermaid-svg-rzX01PkbysltPhMj .cluster-label span p{background-color:transparent;}#mermaid-svg-rzX01PkbysltPhMj .label text,#mermaid-svg-rzX01PkbysltPhMj span{fill:#333;color:#333;}#mermaid-svg-rzX01PkbysltPhMj .node rect,#mermaid-svg-rzX01PkbysltPhMj .node circle,#mermaid-svg-rzX01PkbysltPhMj .node ellipse,#mermaid-svg-rzX01PkbysltPhMj .node polygon,#mermaid-svg-rzX01PkbysltPhMj .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-rzX01PkbysltPhMj .rough-node .label text,#mermaid-svg-rzX01PkbysltPhMj .node .label text,#mermaid-svg-rzX01PkbysltPhMj .image-shape .label,#mermaid-svg-rzX01PkbysltPhMj .icon-shape .label{text-anchor:middle;}#mermaid-svg-rzX01PkbysltPhMj .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-rzX01PkbysltPhMj .rough-node .label,#mermaid-svg-rzX01PkbysltPhMj .node .label,#mermaid-svg-rzX01PkbysltPhMj .image-shape .label,#mermaid-svg-rzX01PkbysltPhMj .icon-shape .label{text-align:center;}#mermaid-svg-rzX01PkbysltPhMj .node.clickable{cursor:pointer;}#mermaid-svg-rzX01PkbysltPhMj .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-rzX01PkbysltPhMj .arrowheadPath{fill:#333333;}#mermaid-svg-rzX01PkbysltPhMj .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-rzX01PkbysltPhMj .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-rzX01PkbysltPhMj .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-rzX01PkbysltPhMj .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-rzX01PkbysltPhMj .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-rzX01PkbysltPhMj .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-rzX01PkbysltPhMj .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-rzX01PkbysltPhMj .cluster text{fill:#333;}#mermaid-svg-rzX01PkbysltPhMj .cluster span{color:#333;}#mermaid-svg-rzX01PkbysltPhMj div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-rzX01PkbysltPhMj .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-rzX01PkbysltPhMj rect.text{fill:none;stroke-width:0;}#mermaid-svg-rzX01PkbysltPhMj .icon-shape,#mermaid-svg-rzX01PkbysltPhMj .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-rzX01PkbysltPhMj .icon-shape p,#mermaid-svg-rzX01PkbysltPhMj .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-rzX01PkbysltPhMj .icon-shape .label rect,#mermaid-svg-rzX01PkbysltPhMj .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-rzX01PkbysltPhMj .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-rzX01PkbysltPhMj .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-rzX01PkbysltPhMj :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

是

否

是

否

左子树 Info

当前节点

右子树 Info

子树中已有 ancestor?

答案直接向上返回

汇总 first / second 是否出现

两者都出现?

当前节点成为 ancestor

ancestor = null

完整代码

package class07;

import utils.TreeNode;

/**
* 找到二叉树中两个指定节点的最近公共祖先。
*/
public class Code06_LowestAncestor {

private static class Info {
final boolean foundFirst;
final boolean foundSecond;
final TreeNode ancestor;

Info(boolean foundFirst, boolean foundSecond, TreeNode ancestor) {
this.foundFirst = foundFirst;
this.foundSecond = foundSecond;
this.ancestor = ancestor;
}
}

public static TreeNode lowestCommonAncestor(
TreeNode root,
TreeNode first,
TreeNode second) {

if (root == null || first == null || second == null) {
return null;
}

return process(root, first, second).ancestor;
}

private static Info process(
TreeNode root,
TreeNode first,
TreeNode second) {

if (root == null) {
return new Info(false, false, null);
}

Info left = process(root.left, first, second);
Info right = process(root.right, first, second);

boolean foundFirst =
left.foundFirst
|| right.foundFirst
|| root == first;

boolean foundSecond =
left.foundSecond
|| right.foundSecond
|| root == second;

TreeNode ancestor = null;

// 如果某一侧已经确定了最近公共祖先，
// 当前节点只负责把这个答案继续向上带。
if (left.ancestor != null) {
ancestor = left.ancestor;
} else if (right.ancestor != null) {
ancestor = right.ancestor;
} else if (foundFirst && foundSecond) {
// 左右子树都没有更低的答案，
// 但当前子树第一次同时拥有两个目标节点，
// 所以当前节点就是最近公共祖先。
ancestor = root;
}

return new Info(foundFirst, foundSecond, ancestor);
}
}

手推：2 和 5

1
/ \\
2 3
/ \\
4 5

处理节点 2：

root == first -> foundFirst = true
右子树找到 5 -> foundSecond = true
左右都没有更低 ancestor

因此：

ancestor = 2

这也说明：

一个节点可以是它自己的祖先。

不存在节点怎么办？

如果某个目标节点不在树中，则根节点最终不会同时满足：

foundFirst && foundSecond

因此 ancestor 会保持 null。

复杂度

易错点

• 按节点值比较，而不是按节点身份比较；
• 找到一侧答案后又被上层覆盖；
• 忘记“某个目标节点本身就是祖先”的情况；
• 默认假设两个节点一定存在于树中。

答案 7：二叉树中的最大距离

返回练习 7

问题回顾

最大距离只有三种来源：

1. 完全在左子树
2. 完全在右子树
3. 穿过当前节点

因此：

maxDistance
=
max(
left.maxDistance,
right.maxDistance,
left.height + right.height + 1
)

这里的 +1 表示当前节点本身。

图解

左侧最深节点
*
|
|
L
\\
当前节点
/
R
|
|
*
右侧最深节点

穿过当前节点的最长路径：

左高度 + 当前节点 1 个 + 右高度

递归信息流

#mermaid-svg-xpH30J9W9is8TI6u{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-xpH30J9W9is8TI6u .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-xpH30J9W9is8TI6u .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-xpH30J9W9is8TI6u .error-icon{fill:#552222;}#mermaid-svg-xpH30J9W9is8TI6u .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-xpH30J9W9is8TI6u .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-xpH30J9W9is8TI6u .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-xpH30J9W9is8TI6u .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-xpH30J9W9is8TI6u .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-xpH30J9W9is8TI6u .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-xpH30J9W9is8TI6u .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-xpH30J9W9is8TI6u .marker{fill:#333333;stroke:#333333;}#mermaid-svg-xpH30J9W9is8TI6u .marker.cross{stroke:#333333;}#mermaid-svg-xpH30J9W9is8TI6u svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-xpH30J9W9is8TI6u p{margin:0;}#mermaid-svg-xpH30J9W9is8TI6u .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-xpH30J9W9is8TI6u .cluster-label text{fill:#333;}#mermaid-svg-xpH30J9W9is8TI6u .cluster-label span{color:#333;}#mermaid-svg-xpH30J9W9is8TI6u .cluster-label span p{background-color:transparent;}#mermaid-svg-xpH30J9W9is8TI6u .label text,#mermaid-svg-xpH30J9W9is8TI6u span{fill:#333;color:#333;}#mermaid-svg-xpH30J9W9is8TI6u .node rect,#mermaid-svg-xpH30J9W9is8TI6u .node circle,#mermaid-svg-xpH30J9W9is8TI6u .node ellipse,#mermaid-svg-xpH30J9W9is8TI6u .node polygon,#mermaid-svg-xpH30J9W9is8TI6u .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-xpH30J9W9is8TI6u .rough-node .label text,#mermaid-svg-xpH30J9W9is8TI6u .node .label text,#mermaid-svg-xpH30J9W9is8TI6u .image-shape .label,#mermaid-svg-xpH30J9W9is8TI6u .icon-shape .label{text-anchor:middle;}#mermaid-svg-xpH30J9W9is8TI6u .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-xpH30J9W9is8TI6u .rough-node .label,#mermaid-svg-xpH30J9W9is8TI6u .node .label,#mermaid-svg-xpH30J9W9is8TI6u .image-shape .label,#mermaid-svg-xpH30J9W9is8TI6u .icon-shape .label{text-align:center;}#mermaid-svg-xpH30J9W9is8TI6u .node.clickable{cursor:pointer;}#mermaid-svg-xpH30J9W9is8TI6u .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-xpH30J9W9is8TI6u .arrowheadPath{fill:#333333;}#mermaid-svg-xpH30J9W9is8TI6u .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-xpH30J9W9is8TI6u .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-xpH30J9W9is8TI6u .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-xpH30J9W9is8TI6u .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-xpH30J9W9is8TI6u .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-xpH30J9W9is8TI6u .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-xpH30J9W9is8TI6u .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-xpH30J9W9is8TI6u .cluster text{fill:#333;}#mermaid-svg-xpH30J9W9is8TI6u .cluster span{color:#333;}#mermaid-svg-xpH30J9W9is8TI6u div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-xpH30J9W9is8TI6u .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-xpH30J9W9is8TI6u rect.text{fill:none;stroke-width:0;}#mermaid-svg-xpH30J9W9is8TI6u .icon-shape,#mermaid-svg-xpH30J9W9is8TI6u .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-xpH30J9W9is8TI6u .icon-shape p,#mermaid-svg-xpH30J9W9is8TI6u .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-xpH30J9W9is8TI6u .icon-shape .label rect,#mermaid-svg-xpH30J9W9is8TI6u .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-xpH30J9W9is8TI6u .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-xpH30J9W9is8TI6u .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-xpH30J9W9is8TI6u :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

左子树height + maxDistance

当前节点

右子树height + maxDistance

height = max左右高度 + 1

throughRoot = 左高 + 右高 + 1

maxDistance 取三者最大

返回 Info

完整代码

package class07;

import utils.TreeNode;

/**
* 二叉树中任意两个节点之间的最大距离。
*
* 本文约定：
* 距离按路径上经过的“节点数”计算。
*/
public class Code07_MaxDistance {

private static class Info {
final int maxDistance;
final int height;

Info(int maxDistance, int height) {
this.maxDistance = maxDistance;
this.height = height;
}
}

public static int maxDistance(TreeNode root) {
if (root == null) {
return 0;
}
return process(root).maxDistance;
}

private static Info process(TreeNode root) {
if (root == null) {
return new Info(0, 0);
}

Info left = process(root.left);
Info right = process(root.right);

int height = Math.max(left.height, right.height) + 1;

// 最大路径如果经过当前节点：
// 左侧最深路径 + 当前节点 + 右侧最深路径。
int throughRoot = left.height + right.height + 1;

int maxDistance =
Math.max(
throughRoot,
Math.max(left.maxDistance, right.maxDistance));

return new Info(maxDistance, height);
}
}

原公式为什么容易少 1？

如果写成：

left.height + right.height

得到的更接近“边数”定义。

例如单节点：

height = 1

如果按节点数，最大距离应该是：

1

如果公式没有 +1，结果会变成 0。

所以这道题写代码前必须先统一：

距离到底按边数还是按节点数？

如果你想按“边数”定义

可以保留：

left.height + right.height

并约定：

单节点距离 = 0

两种定义都可以，关键是全篇一致。

复杂度

易错点

• 没有先约定距离定义；
• 漏掉“最大路径完全在某一棵子树内部”的情况；
• 穿过当前节点时漏掉当前节点自身；
• 把 height 和 maxDistance 当成同一个概念。

答案 8：派对的最大快乐值

返回练习 8

问题回顾

对于每个员工 x，只考虑两个状态：

yes：x 来时，这棵组织子树能获得的最大快乐值
no ：x 不来时，这棵组织子树能获得的最大快乐值

状态转移

如果 x 来：

x 的直接下级全部不能来

所以：

yes = x.happy + Σ child.no

如果 x 不来：

每个下级可以自由选择来或不来

所以：

no = Σ max(child.yes, child.no)

图解

#mermaid-svg-WYB3kprIBWOo567p{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-WYB3kprIBWOo567p .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-WYB3kprIBWOo567p .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-WYB3kprIBWOo567p .error-icon{fill:#552222;}#mermaid-svg-WYB3kprIBWOo567p .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-WYB3kprIBWOo567p .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-WYB3kprIBWOo567p .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-WYB3kprIBWOo567p .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-WYB3kprIBWOo567p .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-WYB3kprIBWOo567p .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-WYB3kprIBWOo567p .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-WYB3kprIBWOo567p .marker{fill:#333333;stroke:#333333;}#mermaid-svg-WYB3kprIBWOo567p .marker.cross{stroke:#333333;}#mermaid-svg-WYB3kprIBWOo567p svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-WYB3kprIBWOo567p p{margin:0;}#mermaid-svg-WYB3kprIBWOo567p .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-WYB3kprIBWOo567p .cluster-label text{fill:#333;}#mermaid-svg-WYB3kprIBWOo567p .cluster-label span{color:#333;}#mermaid-svg-WYB3kprIBWOo567p .cluster-label span p{background-color:transparent;}#mermaid-svg-WYB3kprIBWOo567p .label text,#mermaid-svg-WYB3kprIBWOo567p span{fill:#333;color:#333;}#mermaid-svg-WYB3kprIBWOo567p .node rect,#mermaid-svg-WYB3kprIBWOo567p .node circle,#mermaid-svg-WYB3kprIBWOo567p .node ellipse,#mermaid-svg-WYB3kprIBWOo567p .node polygon,#mermaid-svg-WYB3kprIBWOo567p .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-WYB3kprIBWOo567p .rough-node .label text,#mermaid-svg-WYB3kprIBWOo567p .node .label text,#mermaid-svg-WYB3kprIBWOo567p .image-shape .label,#mermaid-svg-WYB3kprIBWOo567p .icon-shape .label{text-anchor:middle;}#mermaid-svg-WYB3kprIBWOo567p .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-WYB3kprIBWOo567p .rough-node .label,#mermaid-svg-WYB3kprIBWOo567p .node .label,#mermaid-svg-WYB3kprIBWOo567p .image-shape .label,#mermaid-svg-WYB3kprIBWOo567p .icon-shape .label{text-align:center;}#mermaid-svg-WYB3kprIBWOo567p .node.clickable{cursor:pointer;}#mermaid-svg-WYB3kprIBWOo567p .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-WYB3kprIBWOo567p .arrowheadPath{fill:#333333;}#mermaid-svg-WYB3kprIBWOo567p .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-WYB3kprIBWOo567p .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-WYB3kprIBWOo567p .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-WYB3kprIBWOo567p .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-WYB3kprIBWOo567p .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-WYB3kprIBWOo567p .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-WYB3kprIBWOo567p .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-WYB3kprIBWOo567p .cluster text{fill:#333;}#mermaid-svg-WYB3kprIBWOo567p .cluster span{color:#333;}#mermaid-svg-WYB3kprIBWOo567p div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-WYB3kprIBWOo567p .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-WYB3kprIBWOo567p rect.text{fill:none;stroke-width:0;}#mermaid-svg-WYB3kprIBWOo567p .icon-shape,#mermaid-svg-WYB3kprIBWOo567p .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-WYB3kprIBWOo567p .icon-shape p,#mermaid-svg-WYB3kprIBWOo567p .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-WYB3kprIBWOo567p .icon-shape .label rect,#mermaid-svg-WYB3kprIBWOo567p .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-WYB3kprIBWOo567p .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-WYB3kprIBWOo567p .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-WYB3kprIBWOo567p :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

参加

不参加

员工 X

X 是否参加?

所有直接下级必须不参加

yes = X.happy + Σ child.no

每个下级自由选择最优状态

no = Σ max(child.yes, child.no)

为什么这是树形 DP？

普通动态规划会写：

dp[i][state]

这道题只是把数组下标 i 换成了树节点：

dp[employee][come / notCome]

因为组织结构天然是一棵树，所以每个员工的最优决策依赖其孩子状态。

完整代码

package class07;

import java.util.ArrayList;
import java.util.List;

/**
* 派对最大快乐值。
*/
public class Code08_MaxHappy {

/**
* 员工节点。
*/
public static class Employee {
final int happy;
final List<Employee> subordinates;

public Employee(int happy) {
this.happy = happy;
this.subordinates = new ArrayList<>();
}

public void addSubordinate(Employee employee) {
if (employee != null) {
subordinates.add(employee);
}
}
}

/**
* yes：当前员工参加时，本子树最大快乐值。
* no ：当前员工不参加时，本子树最大快乐值。
*/
private static class Info {
final int yes;
final int no;

Info(int yes, int no) {
this.yes = yes;
this.no = no;
}
}

public static int maxHappy(Employee boss) {
if (boss == null) {
return 0;
}

Info info = process(boss);
return Math.max(info.yes, info.no);
}

private static Info process(Employee employee) {
int yes = employee.happy;
int no = 0;

for (Employee child : employee.subordinates) {
Info next = process(child);

// 当前员工来：
// 直接下级必须不来。
yes += next.no;

// 当前员工不来：
// 下级自己选择“来 / 不来”中更优的一种。
no += Math.max(next.yes, next.no);
}

return new Info(yes, no);
}
}

为什么不需要单独处理叶子节点？

叶子员工：

subordinates.isEmpty()

循环不会执行，因此自然得到：

yes = employee.happy
no = 0

这已经是正确基线。

所以可以省掉：

if (root.subordinates.isEmpty()) {
...
}

让代码更统一。

一个小例子

Boss(10)
/ \\
A(5) B(20)
/
C(100)

对于 A：

A 来：
5 + C.no = 5

A 不来：
max(C.yes, C.no) = 100

因此：

A = (yes=5, no=100)

对于 Boss：

Boss 来：
10 + A.no + B.no
= 10 + 100 + 0
= 110

Boss 不来：
max(A.yes, A.no) + max(B.yes, B.no)
= 100 + 20
= 120

最终：

max(110, 120) = 120

复杂度

设员工总数为 N：

每个员工只处理一次。

易错点

• 当前员工来时还允许直接下级来；
• 当前员工不来时，强制所有下级都来；
• 每个下级没有独立取 max(yes, no)；
• subordinates 可能没有初始化，造成空指针；
• 把“直接下级不能来”误解成“所有后代都不能来”。

第三部分：把 8 道题统一成一个递归模板

做到这里，你会发现代码长得越来越像。

它们的共同结构几乎都是：

Info process(Node x) {
if (x == null) {
return baseInfo;
}

Info leftInfo = process(x.left);
Info rightInfo = process(x.right);

// 使用左右信息加工出当前信息
...

return new Info(...);
}

真正变化的不是递归骨架，而是：

Info 里到底装什么？

1. 平衡二叉树

Info:
– isBalanced
– height

父节点需要：

孩子是否平衡
孩子有多高

2. 满二叉树

Info:
– isFull
– height

父节点需要：

孩子是否满
左右高度是否一致

3. BST

Info:
– isBST
– min
– max

父节点需要：

孩子自身是否合法
左边最大值
右边最小值

4. 最大 BST 子树

Info:
– isBST
– min
– max
– size
– maxSubBSTSize

这里开始出现两个层面的信息：

“我自己整体是什么状态”
+
“我内部最优答案是多少”

这类题非常典型。

5. 完全二叉树

Info:
– isFull
– isCBT
– height

为什么需要 isFull？

因为父节点判断自己是不是 CBT 时，必须知道孩子是否处于一种更严格的结构状态。

6. 最近公共祖先

Info:
– foundFirst
– foundSecond
– ancestor

它不再主要统计“数值”，而是在上传：

事件是否发生
+
答案是否已经确定

7. 最大距离

Info:
– height
– maxDistance

这又是经典的：

向上提供辅助信息 height
+
同时维护当前范围最优解 maxDistance

8. 最大快乐值

多叉树虽然没有固定的 left / right，但思路完全相同：

for (Employee child : employee.subordinates) {
Info childInfo = process(child);
...
}

只是把：

左孩子 + 右孩子

变成：

所有孩子

所以树形 DP 的本质从来不是“二叉树”，而是：

子问题构成一棵树，每个父问题依赖孩子问题的有限状态。

第四部分：如何自己设计 Info？

遇到新题时，不要第一反应就写递归。

先问 3 个问题。

问题 1：当前节点最终要解决什么？

例如：

判断平衡？
求最大值？
找某个节点？
统计路径？

问题 2：为了完成这个目标，我缺什么孩子信息？

例如最大距离：

我要知道左边内部最大距离
我要知道右边内部最大距离
我要知道左右能向下延伸多深

于是自然得到：

maxDistance
height

问题 3：这些信息能否在 O(1) 时间合并？

理想状态是：

process(left) -> Info
process(right) -> Info

当前节点只做固定数量计算

这样每个节点只访问一次，整体就能做到：

O(N)

第五部分：树形 DP 的“信息设计”流程图

#mermaid-svg-5WtzhlNy0FxLpz3o{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-5WtzhlNy0FxLpz3o .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-5WtzhlNy0FxLpz3o .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-5WtzhlNy0FxLpz3o .error-icon{fill:#552222;}#mermaid-svg-5WtzhlNy0FxLpz3o .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-5WtzhlNy0FxLpz3o .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-5WtzhlNy0FxLpz3o .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-5WtzhlNy0FxLpz3o .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-5WtzhlNy0FxLpz3o .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-5WtzhlNy0FxLpz3o .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-5WtzhlNy0FxLpz3o .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-5WtzhlNy0FxLpz3o .marker{fill:#333333;stroke:#333333;}#mermaid-svg-5WtzhlNy0FxLpz3o .marker.cross{stroke:#333333;}#mermaid-svg-5WtzhlNy0FxLpz3o svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-5WtzhlNy0FxLpz3o p{margin:0;}#mermaid-svg-5WtzhlNy0FxLpz3o .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-5WtzhlNy0FxLpz3o .cluster-label text{fill:#333;}#mermaid-svg-5WtzhlNy0FxLpz3o .cluster-label span{color:#333;}#mermaid-svg-5WtzhlNy0FxLpz3o .cluster-label span p{background-color:transparent;}#mermaid-svg-5WtzhlNy0FxLpz3o .label text,#mermaid-svg-5WtzhlNy0FxLpz3o span{fill:#333;color:#333;}#mermaid-svg-5WtzhlNy0FxLpz3o .node rect,#mermaid-svg-5WtzhlNy0FxLpz3o .node circle,#mermaid-svg-5WtzhlNy0FxLpz3o .node ellipse,#mermaid-svg-5WtzhlNy0FxLpz3o .node polygon,#mermaid-svg-5WtzhlNy0FxLpz3o .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-5WtzhlNy0FxLpz3o .rough-node .label text,#mermaid-svg-5WtzhlNy0FxLpz3o .node .label text,#mermaid-svg-5WtzhlNy0FxLpz3o .image-shape .label,#mermaid-svg-5WtzhlNy0FxLpz3o .icon-shape .label{text-anchor:middle;}#mermaid-svg-5WtzhlNy0FxLpz3o .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-5WtzhlNy0FxLpz3o .rough-node .label,#mermaid-svg-5WtzhlNy0FxLpz3o .node .label,#mermaid-svg-5WtzhlNy0FxLpz3o .image-shape .label,#mermaid-svg-5WtzhlNy0FxLpz3o .icon-shape .label{text-align:center;}#mermaid-svg-5WtzhlNy0FxLpz3o .node.clickable{cursor:pointer;}#mermaid-svg-5WtzhlNy0FxLpz3o .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-5WtzhlNy0FxLpz3o .arrowheadPath{fill:#333333;}#mermaid-svg-5WtzhlNy0FxLpz3o .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-5WtzhlNy0FxLpz3o .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-5WtzhlNy0FxLpz3o .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-5WtzhlNy0FxLpz3o .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-5WtzhlNy0FxLpz3o .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-5WtzhlNy0FxLpz3o .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-5WtzhlNy0FxLpz3o .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-5WtzhlNy0FxLpz3o .cluster text{fill:#333;}#mermaid-svg-5WtzhlNy0FxLpz3o .cluster span{color:#333;}#mermaid-svg-5WtzhlNy0FxLpz3o div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-5WtzhlNy0FxLpz3o .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-5WtzhlNy0FxLpz3o rect.text{fill:none;stroke-width:0;}#mermaid-svg-5WtzhlNy0FxLpz3o .icon-shape,#mermaid-svg-5WtzhlNy0FxLpz3o .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-5WtzhlNy0FxLpz3o .icon-shape p,#mermaid-svg-5WtzhlNy0FxLpz3o .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-5WtzhlNy0FxLpz3o .icon-shape .label rect,#mermaid-svg-5WtzhlNy0FxLpz3o .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-5WtzhlNy0FxLpz3o .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-5WtzhlNy0FxLpz3o .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-5WtzhlNy0FxLpz3o :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

拿到一道树题

先定义 process 的语义

当前节点要完成什么目标?

父节点需要从孩子获得什么?

把必要内容放进 Info

设计空节点 baseInfo

递归拿到所有孩子 Info

合并出当前 Info

检查是否每个节点只计算一次

第六部分：8 道题放在一张表里

第七部分：建议的验证用例

树题很容易“样例能过，边界错”。

建议至少主动覆盖下面这些结构。

1. 空树

null

检查每道题的对外约定和递归基线是否一致。

2. 单节点

1

重点检查：

• 平衡；
• 满；
• BST；
• 最大 BST 大小；
• CBT；
• 最大距离。

3. 完全左斜树

1
/
2
/
3

重点检查：

• 平衡；
• 满；
• CBT；
• 最大距离。

4. 有右无左

1
\\
2

CBT 必须返回 false。

5. “直接孩子看似满足，但深层破坏 BST”

10
/ \\
5 15
/
6

BST 必须返回 false。

6. 最近公共祖先：一个节点是另一个节点祖先

1
/
2
/
3

查询：

2 和 3

答案应该是：

2

7. 最近公共祖先：目标节点不存在

一个节点不在树中时，应确认你是否希望返回：

null

本文参考实现返回 null。

8. 最大快乐值：一条管理链

A(10)
|
B(100)
|
C(10)

最优答案不是简单选最大单点，而要比较隔层组合。

今日自测

1. 为什么平衡二叉树的 Info 里必须有 height？

查看答案

因为父节点除了要知道左右子树自身是否平衡，还必须比较左右高度差。仅有 isBalanced 无法完成当前节点判断。

2. Perfect Binary Tree 为什么必须要求左右子树等高？

查看答案

因为完美二叉树要求每一层都被填满。即使左右子树各自都满足“节点要么 0 个孩子要么 2 个孩子”，只要高度不同，叶子就不会全部处在同一层。

3. 判断 BST 为什么需要左子树 max 和右子树 min？

查看答案

BST 的约束作用于整棵子树，而不只是直接孩子。左子树所有值都必须小于当前值，因此只需检查其中最大值；右子树所有值都必须大于当前值，因此只需检查其中最小值。

4. 最大 BST 子树中，当前整棵是 BST 时为什么要取 size？

查看答案

因为此时以当前节点为根的整棵子树就是一个合法 BST，它包含当前子树的全部节点，所以最大 BST 大小应等于当前子树总节点数，而不是某个孩子内部最大 BST 的大小再加一。

5. 使用 ArrayDeque 做 CBT 层序遍历时，为什么不能把空孩子直接入队？

查看答案

ArrayDeque 不允许 null 元素。更稳妥的实现是只入队非空节点，并用 leafMode 记录“一旦孩子不双全，之后所有节点必须是叶子”的状态。

6. 最近公共祖先为什么更推荐使用 root == first？

查看答案

题目要找的是两个具体节点。引用比较判断的是节点身份，而 equals 可能被重写为按值比较；当树中存在重复值时，按值比较可能匹配到错误节点。

7. 最大距离为什么要同时返回 height 和 maxDistance？

查看答案

maxDistance 表示子树内部已经出现的最优答案；height 则用于父节点计算“经过父节点”的新候选路径。两者承担不同职责。

8. 派对问题中，当前员工不来时为什么对子节点取 max(yes, no)？

查看答案

当前员工不参加后，不再限制直接下级是否参加，所以每个下级都可以独立选择“参加”和“不参加”中快乐值更大的状态。

加餐挑战

Day 15 复盘清单

• 我能先定义 process(x) 的返回语义，再开始写递归
• 我知道平衡二叉树为什么需要 height + balanced
• 我能区分 Perfect Binary Tree 与“每个节点 0 或 2 个孩子”
• 我知道 BST 不能只比较直接左右孩子
• 我能解释为什么 BST 需要维护子树 min / max
• 我能正确计算“最大 BST 子树”的整棵成立情况
• 我知道 ArrayDeque 不能加入 null
• 我能独立写出 CBT 的 leafMode 层序判定
• 我能解释 CBT 递归法为什么需要 full + cbt + height
• 我知道 LCA 中“答案已经在子树确定”时应该继续上传
• 我会用节点引用而不是只按值识别目标节点
• 我能说清最大距离的三种答案来源
• 我会在写最大距离前先统一“节点数 / 边数”的定义
• 我能写出派对问题的 yes / no 状态转移
• 我理解二叉树递归套路与树形 DP 本质上是同一类思想
• 我遇到新树题时，会先问“父节点到底需要孩子提供什么信息”

一句话总结： Day 15 真正要修炼的不是 8 份递归代码，而是“信息设计能力”：把父节点需要知道的东西压缩进 Info，让每个节点只依赖孩子的有限状态；一旦 Info 设计正确，递归往往只是把这个定义机械地翻译成代码。