作者：不分日夜的我 | 来源：互联网 | 2024-11-05 02:21
二叉树的直径是指树中任意两个叶节点之间最长路径上的节点数量。本文深入解析了计算二叉树直径的算法，并提出了一种优化方法，以提高计算效率和准确性。通过详细的案例分析和性能对比，展示了该优化算法在实际应用中的优势。
The diameter of a tree (sometimes called the width) is the number of nodes on the longest path between two leaves in the tree. The diagram below shows two trees each with diameter nine, the leaves that form the ends of a longest path are shaded (note that there is more than one path in each tree of length nine, but no path longer than nine nodes).
The diameter of a tree T is the largest of the following.
1. the diameter of T‘s left subtree
2. the diameter of T‘s right subtree
3. the longest path between leave nodes that goes through the root of T. This can be computed from the heights of the subtrees of T.
O(n) runtime, O(h) space, h is the height of the given binary tree.
1 class ReturnEntry {
2 int diameter;
3 int height;
4 ReturnEntry(int d, int h) {
5 diameter = d;
6 height = h;
7 }
8 }
9 public class DiameterOfBinaryTree {
10 public static int getDiameter(TreeNode root) {
11 return getDiameterRecur(root).diameter;
12 }
13 private static ReturnEntry getDiameterRecur(TreeNode node) {
14 ReturnEntry ret = new ReturnEntry(0, 0);
15 if(node == null) {
16 return ret;
17 }
18 ReturnEntry left = getDiameterRecur(node.left);
19 ReturnEntry right = getDiameterRecur(node.right);
20 ret.diameter = Math.max(left.height + right.height + 1, Math.max(left.diameter, right.diameter));
21 ret.height = Math.max(left.height, right.height) + 1;
22 return ret;
23 }
24 }
Related Problems
[LintCode] Binary Tree Longest Consecutive Sequence II
[GeeksForGeeks] Diameter of a Binary Tree
京公网安备 11010802041100号