题目概览来源给你一棵二叉树的根节点返回该树的直径。二叉树的直径是指树中任意两个节点之间最长路径的长度。这条路径可能经过也可能不经过根节点root。两节点之间路径的长度由它们之间边数表示。示例 1输入root [1,2,3,4,5]输出3解释3 取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。示例 2输入root [1,2]输出1提示树中节点数目在范围[1, 10^4]内-100 Node.val 100解题分析方法深度遍历如果最大直径经过根节点那么它一定等于左节点的最大深度 右节点的最大深度由于无法确定是否经过根节点我们可以直接遍历所有节点记录经过它的最大深度最后取最大的作为直径。时间复杂度O(n)空间复杂度O(n)/** * Definition for a binary tree node. * public 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 res; public int diameterOfBinaryTree(TreeNode root) { res 0; depth(root); return res; } public int depth(TreeNode root) { if (root null) { return 0; } int left depth(root.left); int right depth(root.right); res Math.max(res, left right); return Math.max(left, right) 1; } }