后序遍历

副标题 / 摘要 LeetCode 124 最容易混淆的地方是：递归到底该返回“整条最大路径”还是“能继续向上接的那一段贡献”。只要把这两个角色分开，这题就会变成一个非常典型的树形 DP。 预计阅读时长：12~15 分钟 标签：Hot100、二叉树、树形DP、DFS、后序遍历 SEO 关键词：Binary Tree Maximum Path Sum, 二叉树中的最大路径和, 树形DP, 单边贡献, 后序遍历, LeetCode 124 元描述：系统讲透 LeetCode 124 的单边贡献返回值、全局最大路径更新、负贡献剪枝与多语言实现。 A — Algorithm（题目与算法） 题目还原 二叉树中的一条路径定义为： 由若干个节点组成 相邻节点之间必须有边相连 同一个节点在一条路径里最多出现一次 路径至少包含一个节点 路径不一定经过根节点 路径和就是路径上所有节点值之和。 题目要求返回整棵树里的最大路径和。 输入输出 名称 类型 描述 root TreeNode 二叉树根节点 返回值 int 最大路径和 示例 1 输入：root = [1,2,3] 输出：6 解释：最优路径是 2 -> 1 -> 3，路径和为 6。 示例 2 输入：root = [-10,9,20,null,null,15,7] 输出：42 解释：最优路径是 15 -> 20 -> 7，路径和为 42。 提示 树中节点数目范围是 [1, 3 * 10^4] -1000 <= Node.val <= 1000 目标读者 已经做过 543，但还没完全理解“树上路径题”返回值该如何设计的学习者 一写最大路径和就会把“经过当前节点的完整路径”和“向上返回的贡献”混掉的开发者 想系统掌握树形 DP 基本套路的读者 背景 / 动机 这题的关键训练点是： ...

副标题 / 摘要 LeetCode 543 最容易混乱的点是：递归函数到底应该返回“高度”还是“直径”。这题的稳定写法是后序遍历时向上返回高度，同时在每个节点尝试更新“经过当前节点的最长路径”。理解这个分工后，树形 DP 会一下子清楚很多。 预计阅读时长：10~13 分钟 标签：Hot100、二叉树、树形DP、DFS、后序遍历 SEO 关键词：Diameter of Binary Tree, 二叉树的直径, 树形DP, 高度回传, DFS, LeetCode 543 元描述：系统讲透 LeetCode 543 的后序高度回传法，包含递推推导、工程迁移、复杂度分析与多语言实现。 A — Algorithm（题目与算法） 题目还原 给你一棵二叉树的根节点 root，返回该树的直径。 二叉树的直径指的是： 树中任意两个节点之间最长路径的长度 这条路径可以经过根节点，也可以不经过根节点 路径长度按边数计算 输入输出 名称 类型 描述 root TreeNode 二叉树根节点 返回 int 树的直径（最长路径边数） 示例 1 输入：root = [1,2,3,4,5] 输出：3 解释：长度为 3 ，取路径 [4,2,1,3] 或 [5,2,1,3] 。 示例 2 输入：root = [1,2] 输出：1 提示 树中节点数目在范围 [1, 10^4] 内 -100 <= Node.val <= 100 目标读者 已经会写树深度递归，准备进入树形 DP 视角的学习者 容易把“返回值”和“全局答案”混在一起的开发者 在工程里处理层级传播链、最长链路或树状结构跨度问题的工程师 背景 / 动机 看到“二叉树的直径”，很多人第一反应会是： ...

副标题 / 摘要 LeetCode 236 的真正难点不是“记住 LCA 模板”，而是先定义清楚：递归函数到底要向父节点返回什么信息。只要这个返回值语义稳定，整题就会自然落成一段非常短但非常强的后序递归。 预计阅读时长：11~14 分钟 标签：Hot100、二叉树、LCA、DFS、后序遍历 SEO 关键词：Lowest Common Ancestor of a Binary Tree, 二叉树的最近公共祖先, LCA, 后序遍历, DFS, LeetCode 236 元描述：系统讲透 LeetCode 236 的后序返回值定义、节点自祖先规则、递归推导过程、工程迁移和多语言实现。 A — Algorithm（题目与算法） 题目还原 给定一棵二叉树，找到该树中两个指定节点 p 和 q 的最近公共祖先。 最近公共祖先（LCA）的定义是： x 同时是 p 和 q 的祖先 在满足上面条件的节点里，x 的深度尽可能大 一个节点也可以是它自己的祖先 输入输出 名称 类型 描述 root TreeNode 二叉树根节点 p, q TreeNode 树中的两个指定节点；示例输入里用它们的唯一值表示 返回 TreeNode p 和 q 的最近公共祖先 示例 1 输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 输出：3 解释：节点 5 和节点 1 的最近公共祖先是节点 3 。 示例 2 输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 输出：5 解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。 示例 3 输入：root = [1,2], p = 1, q = 2 输出：1 提示 树中节点数目在范围 [2, 10^5] 内 -10^9 <= Node.val <= 10^9 所有 Node.val 互不相同 p != q p 和 q 均存在于给定的二叉树中 目标读者 已经会写普通树递归，但一到“最近公共祖先”就容易卡在返回值定义上的学习者 想把后序分治写法固定成稳定模板的开发者 在工程里处理组织树、组件树、目录树共享祖先问题的工程师 背景 / 动机 很多人第一次做 236，会下意识想到： ...