543. 二叉树的直径

---

题目

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

示例： 示例 1:

输入: root = [1,2,3,4,5]
输出: 3
解释: 路径 [4,2,1,3] 或 [5,2,1,3] 的长度为 3。

示例 2:

输入: root = [1,2]
输出: 1

---

解题思路

核心方法

递归法：在计算每个节点左右子树深度的同时，维护一个全局变量记录当前最长路径（即左右子树深度之和），最终返回该全局变量。

算法步骤

1. 定义全局变量：用一个变量 ans 记录当前最长路径的长度。
2. 递归计算深度：对于每个节点，递归计算其左子树和右子树的深度。
3. 更新最长路径：当前节点的路径长度为左子树深度 + 右子树深度，若该值大于 ans，则更新 ans。
4. 返回当前深度：当前节点的深度为左右子树深度的最大值 + 1，供父节点计算使用。
5. 返回结果：递归结束后，ans 即为二叉树的直径。

---

代码实现

递归法（Java）

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    int ans = 0;
    
    public int diameterOfBinaryTree(TreeNode root) {
        getLength(root);
        return ans;
    }
    
    public int getLength(TreeNode root) {
        if (root == null) return 0;
        int left = getLength(root.left);
        int right = getLength(root.right);
        ans = Math.max(ans, left + right);
        return Math.max(left, right) + 1;
    }
}

---

复杂度分析

• 时间复杂度：O(n)，其中 n 是二叉树的节点数。每个节点会被访问一次。
• 空间复杂度：O(h)，h 是二叉树的高度。递归栈的深度取决于树的高度，最坏情况下（链状树）为 O(n)。

---

总结

1. 该方法通过一次递归同时计算深度和直径，时间效率较高。
2. 关键在于理解直径的定义：任意两节点间的最长路径，不一定经过根节点，因此需要在递归过程中维护全局最大值。
3. 递归返回的是当前节点的深度，而直径则是在递归过程中动态更新的。

---