题目

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

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

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

解题思路

1. 最长长度可以理解为左子树最长路径加上右子树最长路径；
2. 因此可以通过递归来获取每个节点左右子树的最长长度，最后得到根节点的最长直径；

代码展示

class Solution {private int ans;public int diameterOfBinaryTree(TreeNode root) {dfs(root);return ans;}public int dfs(TreeNode root){if(root == null) {return -1;}int leftLength = dfs(root.left) + 1;int rightLength = dfs(root.right) + 1;ans = Math.max(ans, leftLength + rightLength);return Math.max(leftLength, rightLength);}
}