树与图简单1 种解法
#543二叉树的直径
返回二叉树任意两节点间最长路径的边数。
#二叉树#深度优先搜索#后序遍历
原题
给你一棵二叉树的根节点，返回该树的 直径 。
二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。
两节点之间路径的 长度 由它们之间边数表示。
示例 1：
输入：root = [1,2,3,4,5] 输出：3 解释：3 ，取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。
示例 2：
输入：root = [1,2] 输出：1
提示：
- 树中节点数目在范围
[1, 104]内 -100 <= Node.val <= 100
解题主线
- 经过某节点的最长路径边数等于左右子树高度之和。
解法 1：后序高度与局部答案
后序返回高度，同时用方法内数组更新所有节点的左右高度和。
-
时间复杂度： O(n)
-
空间复杂度： O(h)
import java.util.*;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
}
}
class Solution {
public int diameterOfBinaryTree(TreeNode root) {
int[] diameter = new int[1];
height(root, diameter);
return diameter[0];
}
private int height(TreeNode node, int[] diameter) {
// 空子树高度为 0，使叶子节点返回高度 1
if (node == null) return 0;
// 后序获取左右高度后，才能计算经过当前节点的路径
int left = height(node.left, diameter);
int right = height(node.right, diameter);
// 左右高度之和恰好是该路径的边数
diameter[0] = Math.max(diameter[0], left + right);
// 向父节点只返回较长一侧的节点高度
return Math.max(left, right) + 1;
}
}边界与易错点
- 答案按边计数，而高度递归按节点层数返回。
- 最大直径必须在每次公开方法调用时重置。
整理来源
由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。
leetcode/src/main/java/tree/Q543_tree_diameter.java