Diameter of Binary Tree
DFS returns subtree depth; meanwhile track best left + right pair at any bend.
3 min read
tree dfs
Problem#
Return the length (in edges) of the longest path between any two nodes in a binary tree.
Examples#
[1,2,3,4,5]→3(4-2-1-3 or 5-2-1-3)[1,2]→1
Constraints#
- The number of nodes is in
[1, 10^4].
Approach#
DFS each node returns its subtree depth. At each node, the candidate diameter through it is leftDepth + rightDepth. Track the global max.
Solution#
class Solution {public: int diameterOfBinaryTree(TreeNode* root) { int best = 0; function<int(TreeNode*)> dfs = [&](TreeNode* u) -> int { if (!u) return 0; int l = dfs(u->left); int r = dfs(u->right); best = max(best, l + r); return 1 + max(l, r); }; dfs(root); return best; }};func diameterOfBinaryTree(root *TreeNode) int { best := 0 var dfs func(u *TreeNode) int dfs = func(u *TreeNode) int { if u == nil { return 0 } l := dfs(u.Left) r := dfs(u.Right) if l+r > best { best = l + r } if l > r { return 1 + l } return 1 + r } dfs(root) return best}from typing import Optional
class Solution: def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int: best = 0 def dfs(u: Optional[TreeNode]) -> int: nonlocal best if not u: return 0 l = dfs(u.left) r = dfs(u.right) best = max(best, l + r) return 1 + max(l, r) dfs(root) return bestvar diameterOfBinaryTree = function(root) { let best = 0; const dfs = (u) => { if (!u) return 0; const l = dfs(u.left); const r = dfs(u.right); best = Math.max(best, l + r); return 1 + Math.max(l, r); }; dfs(root); return best;};class Solution { private int best = 0;
public int diameterOfBinaryTree(TreeNode root) { dfs(root); return best; }
private int dfs(TreeNode u) { if (u == null) return 0; int l = dfs(u.left); int r = dfs(u.right); best = Math.max(best, l + r); return 1 + Math.max(l, r); }}function diameterOfBinaryTree(root: TreeNode | null): number { let best = 0; const dfs = (u: TreeNode | null): number => { if (!u) return 0; const l = dfs(u.left); const r = dfs(u.right); best = Math.max(best, l + r); return 1 + Math.max(l, r); }; dfs(root); return best;}Editorial#
Same shape as Binary Tree Maximum Path Sum — return the extendable arm depth, track the bend separately. Depth-in-edges differs from depth-in-nodes by one; the formula uses 1 + max(l, r) for “depth as 1 plus deeper child”.
Complexity#
- Time: O(n).
- Space: O(h).
Concept revision#
Related#