題目
給你一棵二叉樹的根節點，返回該樹的?直徑?。
二叉樹的?直徑?是指樹中任意兩個節點之間最長路徑的?長度?。這條路徑可能經過也可能不經過根節點?
root?。兩節點之間路徑的?長度?由它們之間邊數表示。
解題思路
- 最長長度可以理解為左子樹最長路徑加上右子樹最長路徑；
- 因此可以通過遞歸來獲取每個節點左右子樹的最長長度，最后得到根節點的最長直徑；
代碼展示
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);}
}
)
