Java实现 LeetCode 543. 二叉树的直径（遍历树）

╰半夏微凉° 2023-07-18 09:12 74阅读 0赞

## 543. 二叉树的直径 ##

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

示例 :  
给定二叉树

1
         / \
        2   3
       / \     
      4   5

返回 3, 它的长度是路径 \[4,2,1,3\] 或者 \[5,2,1,3\]。

注意：两结点之间的路径长度是以它们之间边的数目表示。  
PS：  
二叉树的直径不一定过根节点，因此需要去搜一遍所有子树(例如以root，root.left, root.right…为根节点的树)对应的直径，取最大值。  
root的直径 = root左子树高度 + root右子树高度  
root的高度 = max \{root左子树高度, root右子树高度\} + 1

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
    
    
    class Solution { 
         private int max = 0;
    
        public int diameterOfBinaryTree(TreeNode root) { 
            dfs(root);
            return max;
        }
    
        private int dfs(TreeNode root) { 
            if (root == null) { 
                return 0;
            }
            int leftHeight = dfs(root.left), rightHeight = dfs(root.right);
            max = Math.max(leftHeight + rightHeight, max);
            return Math.max(leftHeight, rightHeight) + 1;
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，74人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode-543. 二叉树的直径

目录题目分析错误实例正确实例题目来源 [543. 二叉树的直径][543.] 题目分析 1.如何求得两个叶子

╰半橙微兮°/ 2024年03月27日 14:08/ 0 赞/ 172 阅读

相关 Java实现 LeetCode 543. 二叉树的直径（遍历树）

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

╰半夏微凉°/ 2023年07月18日 09:12/ 0 赞/ 75 阅读

相关 leetcode543.二叉树的直径

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

迷南。/ 2023年07月13日 08:21/ 0 赞/ 88 阅读

相关 leetcode 543. 二叉树的直径

解题思路其实一个非常暴力的方法就是将每个节点都当做根节点，然后求左右子树的高度，相加。最后取最大值即可。但其实这样的n^2 暴力，可以优化到o(n). 方法是

深碍√TFBOYSˉ_/ 2023年07月13日 03:39/ 0 赞/ 93 阅读

相关 leetcode543. 二叉树的直径

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

╰半橙微兮°/ 2023年07月06日 13:08/ 0 赞/ 97 阅读

相关 Leetcode 543. 二叉树的直径

Leetcode 543. 二叉树的直径 1、问题分析 2、问题解决 3、总结 1、问题分析题目链接：[https://leetcode-cn

小灰灰/ 2023年02月14日 03:10/ 0 赞/ 129 阅读

相关 leetcode543二叉树的直径

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

傷城~/ 2022年08月29日 10:58/ 0 赞/ 258 阅读

相关 leetcode 543. 二叉树的直径(python)

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

- 日理万妓/ 2022年05月20日 07:38/ 0 赞/ 282 阅读

相关【LeetCode】543. 二叉树的直径

题目链接：[https://leetcode-cn.com/problems/diameter-of-binary-tree/description/][https_leetc

Dear 丶/ 2022年05月13日 17:29/ 0 赞/ 271 阅读

相关 LeetCode-543. 二叉树的直径

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

柔光的暖阳◎/ 2022年01月28日 17:57/ 0 赞/ 285 阅读