leetcode 543. 二叉树的直径（Java版）

题目

https://leetcode-cn.com/problems/diameter-of-binary-tree/

题解 1：暴力法

暴力解法：遍历这棵树，当以每个节点为根时，计算 距离，取最大值作为最终结果。

其中，距离 = 左 深度 + 右 深度。

其中，深度的计算用 getDepth() 来定义。

/* Definition for a binary tree node. */ 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;} }public class Solution {int max = 0;public int diameterOfBinaryTree(TreeNode root) {inOrder(root);return max;}// 先序遍历public void inOrder(TreeNode node) {if (node == null) return;int distance = getDepth(node.left, 0) + getDepth(node.right, 0);if (distance > max) max = distance;inOrder(node.left);inOrder(node.right);}// 计算当前节点为根时的树深度public int getDepth(TreeNode node, int depth) {if (node == null) return depth;else return Math.max(getDepth(node.left, depth + 1), getDepth(node.right, depth + 1));} }

此方法效率很差

题解 2：官方题解

class Solution {int ans;public int diameterOfBinaryTree(TreeNode root) {ans = 1;depth(root);return ans - 1;}public int depth(TreeNode node) {if (node == null) {return 0; // 访问到空节点了，返回0}int L = depth(node.left); // 左儿子为根的子树的深度int R = depth(node.right); // 右儿子为根的子树的深度ans = Math.max(ans, L+R+1); // 计算d_node即L+R+1 并更新ansreturn Math.max(L, R) + 1; // 返回该节点为根的子树的深度} }作者：LeetCode-Solution 链接：https://leetcode-cn.com/problems/diameter-of-binary-tree/solution/er-cha-shu-de-zhi-jing-by-leetcode-solution/

总结

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

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