LeetCode：543. Diameter of Binary Tree(找出二叉树中最大的直径)

秒速五厘米 2022-04-11 13:47 170阅读 0赞

> **文章最前**： 我是Octopus，这个名字来源于我的中文名--章鱼；我热爱编程、热爱算法、热爱开源。
> 
> 这博客是记录我学习的点点滴滴，如果您对 Python、Java、AI、算法有兴趣，可以关注我的动态，一起学习，共同进步。

**相关文章：**

1.  **[LeetCode：55. Jump Game（跳远比赛）][LeetCode_55. Jump Game]**
2.  **[Leetcode：300. Longest Increasing Subsequence（最大增长序列）][Leetcode_300. Longest Increasing Subsequence]**
3.  **[LeetCode：560. Subarray Sum Equals K（找出数组中连续子串和等于k）][LeetCode_560. Subarray Sum Equals K_k]**

--------------------

**文章目录：**

java实现方法1：

python实现方式1：

源码地址：

--------------------

### **题目描述：** ###

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。

示例 :

给定二叉树：
    
              1
             / \
            2   3
           / \     
          4   5    
    返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。

注意：两结点之间的路径长度是以它们之间边的数目表示。

--------------------

来源：力扣（LeetCode）

--------------------

### java实现方法1： ###

private int maxDiameter = 0;
    
        /**
         * 求最大直径
         *
         * @param root 根节点
         * @return 最大直径
         */
        public int diameterOfBinaryTree(TreeNode root) {
            if (root == null) {
                return 0;
            }
            helper(root);
            return maxDiameter;
        }
    
        /**
         * 最大直径
         *
         * @param root 根节点
         * @return 最大直径
         */
        private int helper(TreeNode root) {
            if (root.left == null && root.right == null) {
                return 0;
            }
            int left = root.left == null ? 0 : helper(root.left) + 1;
            int right = root.right == null ? 0 : helper(root.right) + 1;
            maxDiameter = Math.max(left + right, maxDiameter);
            return Math.max(left, right);
        }

时间复杂度：O(n^2)

空间复杂度：O(n)

--------------------

### python实现方式1： ###

max_deep = 0
    
    
    class Solution:
        def diameter_of_binary_tree(self, root: TreeNode) -> int:
            '''
                最大直径
            Args:
                root: 根节点
            Returns:
                最大深度
            '''
            global max_deep
            if not root:
                return 0
            self.search_helper(root)
            return max_deep
    
        def search_helper(self, root: TreeNode) -> int:
            '''
                求最大直径
            Args:
                root: 根节点
            Returns:
               最大深度
            '''
            global max_deep
            if not root.left and not root.right:
                return 0
            left_deep = self.search_helper(root.left) + 1 if root.left else 0
            right_deep = self.search_helper(root.right) + 1 if root.right else 0
            max_deep = max(max_deep, left_deep + right_deep)
            return max(left_deep, right_deep)

时间复杂度：O(n^2)

空间复杂度：O(n)

--------------------

## 源码地址： ##

[https://github.com/zhangyu345293721/leetcode][https_github.com_zhangyu345293721_leetcode]

[LeetCode_55. Jump Game]: https://blog.csdn.net/zy345293721/article/details/84991870
[Leetcode_300. Longest Increasing Subsequence]: https://blog.csdn.net/zy345293721/article/details/84984249
[LeetCode_560. Subarray Sum Equals K_k]: https://blog.csdn.net/zy345293721/article/details/84952201
[https_github.com_zhangyu345293721_leetcode]: https://github.com/zhangyu345293721/leetcode