543. 二叉树的直径
题目描述
输入一棵二叉树的根节点 root，树用层序数组表示，例如 [1,2,3,4,5]，null 表示空位。
树中任取两个节点，它们之间的路径长度按经过的边数计算。所有节点对里最长的那条路径长度称为这棵树的直径。这条路径不一定要经过根节点。
返回树的直径。
示例 1
输入：root = [1,2,3,4,5] 输出：3
解释：路径 4 -> 2 -> 1 -> 3（或 5 -> 2 -> 1 -> 3）有 3 条边。
示例 2
输入：root = [1,2] 输出：1
解释：只有两个节点，它们之间有 1 条边。
数据范围
- 节点数在
[1, 10^4]范围内。 -100 <= Node.val <= 100
解题思路：递归后序求高度
后序求子树高度；每个节点的左右高度之和是经过该节点的候选直径。
为什么正确
height 返回节点数高度，best 记录所有已处理节点的最大左右高度之和。
复杂度分析
时间 O(n)，递归栈 O(h)；h 为树高，最坏可为 n；Python 递归受解释器递归深度限制，深链树应改用显式栈。
易错点
不要把返回给父节点的高度当成直径；直径可以同时使用左右分支。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def diameterOfBinaryTree(self, root):
best = 0
def height(node):
nonlocal best
if not node:
return 0
left = height(node.left)
right = height(node.right)
best = max(best, left + right)
return 1 + max(left, right)
height(root)
return bestclass Solution {
private int best;
public int diameterOfBinaryTree(TreeNode root) {
best = 0;
height(root);
return best;
}
private int height(TreeNode node) {
if (node == null)
return 0;
int left = height(node.left);
int right = height(node.right);
best = Math.max(best, left + right);
return 1 + Math.max(left, right);
}
}class Solution {
public:
int diameterOfBinaryTree(TreeNode* root) {
int best = 0;
function<int(TreeNode*)> height = [&](TreeNode* node) {
if (!node)
return 0;
int left = height(node->left);
int right = height(node->right);
best = max(best, left + right);
return 1 + max(left, right);
};
height(root);
return best;
}
};func diameterOfBinaryTree(root *TreeNode) int {
best := 0
var height func(node *TreeNode) int
height = func(node *TreeNode) int {
if node == nil {
return 0
}
left := height(node.Left)
right := height(node.Right)
best = max(best, left+right)
return 1 + max(left, right)
}
height(root)
return best
}var diameterOfBinaryTree = function(root) {
let best = 0;
const height = (node) => {
if (!node)
return 0;
const left = height(node.left);
const right = height(node.right);
best = Math.max(best, left + right);
return 1 + Math.max(left, right);
};
height(root);
return best;
};function diameterOfBinaryTree(root: TreeNode | null): number {
let best = 0;
const height = (node: TreeNode | null): number => {
if (!node)
return 0;
const left = height(node.left);
const right = height(node.right);
best = Math.max(best, left + right);
return 1 + Math.max(left, right);
};
height(root);
return best;
};其他解法
两种解法都是后序遍历，在每个节点用左右高度之和更新答案；递归简洁，显式栈规避递归深度限制。
解法 2：显式栈后序遍历 时间 O(n)，空间 O(n)
用栈模拟后序遍历。每个节点第一次出栈时重新压入并标记“已展开”，再压入左右子节点。第二次出栈时左右子树已处理完，从哈希表取出两边高度，更新答案并记录自己的高度。
不受递归深度限制，深链树也不会栈溢出。代价是要用哈希表保存每个节点的高度，代码也更长。
class Solution:
def diameterOfBinaryTree(self, root):
if not root:
return 0
best = 0
height = {None: 0}
stack = [(root, False)]
while stack:
node, done = stack.pop()
if done:
left = height[node.left]
right = height[node.right]
best = max(best, left + right)
height[node] = 1 + max(left, right)
else:
stack.append((node, True))
if node.right:
stack.append((node.right, False))
if node.left:
stack.append((node.left, False))
return bestclass Solution {
public int diameterOfBinaryTree(TreeNode root) {
if (root == null) return 0;
int best = 0;
Map<TreeNode, Integer> height = new HashMap<>();
Deque<Object[]> stk = new ArrayDeque<>();
stk.push(new Object[]{root, false});
while (!stk.isEmpty()) {
Object[] top = stk.pop();
TreeNode node = (TreeNode) top[0];
boolean done = (Boolean) top[1];
if (done) {
int left = height.getOrDefault(node.left, 0);
int right = height.getOrDefault(node.right, 0);
best = Math.max(best, left + right);
height.put(node, 1 + Math.max(left, right));
} else {
stk.push(new Object[]{node, true});
if (node.right != null) stk.push(new Object[]{node.right, false});
if (node.left != null) stk.push(new Object[]{node.left, false});
}
}
return best;
}
}class Solution {
public:
int diameterOfBinaryTree(TreeNode* root) {
if (!root) return 0;
int best = 0;
unordered_map<TreeNode*, int> height;
height[nullptr] = 0;
vector<pair<TreeNode*, bool>> stk = {{root, false}};
while (!stk.empty()) {
auto [node, done] = stk.back();
stk.pop_back();
if (done) {
int left = height[node->left];
int right = height[node->right];
best = max(best, left + right);
height[node] = 1 + max(left, right);
} else {
stk.push_back({node, true});
if (node->right) stk.push_back({node->right, false});
if (node->left) stk.push_back({node->left, false});
}
}
return best;
}
};func diameterOfBinaryTree(root *TreeNode) int {
if root == nil {
return 0
}
type item struct {
node *TreeNode
done bool
}
best := 0
height := map[*TreeNode]int{}
stk := []item{{root, false}}
for len(stk) > 0 {
top := stk[len(stk)-1]
stk = stk[:len(stk)-1]
node := top.node
if top.done {
left := height[node.Left]
right := height[node.Right]
best = max(best, left+right)
height[node] = 1 + max(left, right)
} else {
stk = append(stk, item{node, true})
if node.Right != nil {
stk = append(stk, item{node.Right, false})
}
if node.Left != nil {
stk = append(stk, item{node.Left, false})
}
}
}
return best
}var diameterOfBinaryTree = function(root) {
if (!root) return 0;
let best = 0;
const height = new Map();
const stk = [[root, false]];
while (stk.length) {
const [node, done] = stk.pop();
if (done) {
const left = node.left ? height.get(node.left) : 0;
const right = node.right ? height.get(node.right) : 0;
best = Math.max(best, left + right);
height.set(node, 1 + Math.max(left, right));
} else {
stk.push([node, true]);
if (node.right) stk.push([node.right, false]);
if (node.left) stk.push([node.left, false]);
}
}
return best;
};function diameterOfBinaryTree(root: TreeNode | null): number {
if (!root) return 0;
let best = 0;
const height = new Map<TreeNode, number>();
const stk = [[root, false]] as [TreeNode, boolean][];
while (stk.length) {
const [node, done] = stk.pop()!;
if (done) {
const left = node.left ? height.get(node.left)! : 0;
const right = node.right ? height.get(node.right)! : 0;
best = Math.max(best, left + right);
height.set(node, 1 + Math.max(left, right));
} else {
stk.push([node, true]);
if (node.right) stk.push([node.right, false]);
if (node.left) stk.push([node.left, false]);
}
}
return best;
}