题目描述

给你一棵二叉树的根节点，返回该树的 直径 。

二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。

两节点之间路径的 长度 由它们之间边数表示。

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

题目分析

树的直径是 根节点或子节点的（左子树高度+右子树高度），取最大值。因此使用递归计算一次 root 的高度，过程中就可以得到每个节点的左子树高度和右子树高度，维护 ans 即可

Java

private int ans = 0;

public int diameterOfBinaryTree(TreeNode root) {
    if (root == null) {
        return 0;
    }
    ans = 0;
    height(root);
    return ans;
}

private int height(TreeNode node) {
    if (node == null) {
        return 0;
    }
    int left = height(node.left);
    int right = height(node.right);
    ans = Math.max(ans, left + right);
    return Math.max(left, right) + 1;
}

Kotlin

private var ans = 0

fun diameterOfBinaryTree(root: TreeNode?): Int {
    if (root == null) {
        return 0
    }
    ans = 0
    height(root)
    return ans
}

private fun height(root: TreeNode?): Int {
    if (root == null) {
        return 0
    }
    val left = height(root.left)
    val right = height(root.right)
    ans = max(ans, left + right)
    return max(left, right) + 1
}