【LeetCode 543】算法：二叉树的直径

题目：
给你一棵二叉树的根节点，返回该树的 直径 。
二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。
两节点之间路径的 长度 由它们之间边数表示。

算法思路：

• 直径 = 左子树最大深度 + 右子树最大深度（经过当前节点）。
  
• 对每个节点都算一次，全局保留最大值即可。
  
• 一次 DFS 即可：在求深度的同时更新直径。
  

复杂度：
时间：O(n)，每个节点访问一次
空间：O(h)，递归栈深度（h 为树高）
Java 代码实现：

1. /**
2. * Definition for a binary tree node.
3. * public class TreeNode {
4. *     int val;
5. *     TreeNode left;
6. *     TreeNode right;
7. *     TreeNode() {}
8. *     TreeNode(int val) { this.val = val; }
9. *     TreeNode(int val, TreeNode left, TreeNode right) {
10. *         this.val = val;
11. *         this.left = left;
12. *         this.right = right;
13. *     }
14. * }
15. */
16. class Solution {
18.     private int max = 0;  // 全局最大直径
20.     public int diameterOfBinaryTree(TreeNode root) {
21.         if(root==null)  return 0;
22.         if(root.left==null && root.right==null)  return 0;
23.         depth(root);
24.         return max;
25.     }
27.     // 返回以 node 为根的子树最大深度
28.     private int depth(TreeNode node){
29.         if(node==null)  return 0;
30.         if(node.left==null && node.right==null) return 1;
31.         
32.         // 计算左右子树的深度
33.         int leftDepth = depth(node.left);
34.         int rightDepth = depth(node.right);
35.         
36.         // 经过当前节点的直径
37.         int d = leftDepth + rightDepth;
38.         // 更新最大直径
39.         max = Math.max(max, d);
40.         
41.         // 返回当前子树深度
42.         int h = 1 + Math.max(leftDepth, rightDepth);
43.         return h;
44.     }
46. }

复制代码

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！