文章目录

• 题目描述
• 思路 & 代码

题目描述

思路 & 代码

• 由这个结论考虑：直径中一定有一个父结点，那么当前直径长度就是：
  当前父结点的左子树深度 + 右子树深度
• 那么，只要遍历所有结点的最长直径值即可
• 流程：在找每一个结点的最深值的遍历过程中维护ans，遍历结束后返回ans。

/*** 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 ans = 0;public int diameterOfBinaryTree(TreeNode root) {// 跑结果，维护ansmaxDepth(root);return ans;}// 函数功能：返回 root 可达的最深层// 可以遍历所有结点的最长直径int maxDepth(TreeNode root){if(root == null){return 0;}// 取左右子结点的可达最深层int right = maxDepth(root.right);int left = maxDepth(root.left);// 在这个过程中，维护ans：ans一定是某个结点的左右子树结合成的。ans = Math.max(ans, right + left);// root的maxDepth就是左 or 右的 maxDepth + 1return Math.max(right,left) + 1;} }

• 时间复杂度O(n)，自底向上把全部结点遍历了一遍。
• 无注释版

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

总结

以上是生活随笔为你收集整理的【LeetCode笔记】543. 二叉树的直径（Java、dfs、二叉树）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。