【Check 49】2024-04-11 - 543. 二叉树的直径

[larscheng]

543. 二叉树的直径

[larscheng]

思路

直径 = 最长路径的长度 = 最长路径经过的边数 = 最长路径节点数-1

• 根据根节点，取得当前根节点的左右子树深度，可得当前根节点所在最长路径的节点总数l+r+1
• 递归获取不同根节点所在最长路径的节点数最大值
• 根据节点数最大值-1，可得最长路径经过的边数，即为二叉树直径

  代码

class Solution {

//树中节点大于1，最小直径为1
int ans = 1;

public int diameterOfBinaryTree(TreeNode root) {
    depth(root);
    return ans - 1;
}

private int depth(TreeNode root) {
    if (root == null) {
        return 0;
    }
    int l = depth(root.left);
    int r = depth(root.right);

    //当前根节点所在最长路径中的节点数
    ans = Math.max(ans, l + r + 1);

    //返回当前根节点(root)下子树的最大深度
    return Math.max(l, r) + 1;
}

}

### 复杂度
- 时间复杂度：O(n)
- 空间复杂度：O(n)