【LeetCode】20. Diameter Binary Tree· 二叉树的直径

灰太狼 2024-04-06 11:36 41阅读 0赞

### 题目描述 ###

#### 英文版描述 ####

Given the `root` of a binary tree, return *the length of the* ***diameter*** *of the tree*.

The **diameter** of a binary tree is the **length** of the longest path between any two nodes in a tree. This path may or may not pass through the `root`.

The **length** of a path between two nodes is represented by the number of edges between them.

#### 英文版地址 ####

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

#### 中文版描述 ####

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

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

**提示：**

*  两结点之间的路径长度是以它们之间边的数目表示

#### 中文版地址 ####

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

### 解题思路 ###

现在一看到二叉树就想到**深度优先**(￣∇￣)

我们可以先做一个转化，这个问题其实可以变为求每个节点的左右子树之和的最大值，我们设置1个变量`maxValue`用于存储最大值，每求到一个节点的左右子树之和，就跟`maxValue`做比较，大于`maxValue`就将`maxValue`的值替换为当前值，小于`maxValue`则不做处理，继续下一个节点，直到所有节点计算完毕，返回`maxValue`

### 解题方法 ###

#### 俺这版 ####

![e308c46ae19d43dbb3a8e47355ab63da.png][]

/**
     * 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 maxValue;
    
        public int diameterOfBinaryTree(TreeNode root) {
            maxValue = 0;
            getTreeHeight(root);
            return maxValue - 1;
        }
    
        public int getTreeHeight(TreeNode root) {
            if (root == null) {
                return 0;
            }
            int leftHeight = getTreeHeight(root.left);
            int rightHeight = getTreeHeight(root.right);
            maxValue = Math.max(maxValue, leftHeight + rightHeight + 1);
            return Math.max(leftHeight, rightHeight) + 1;
    
        }
    }

**复杂度分析**

对于二叉树来说，有多少个节点需要计算多少次深度，所以其时间复杂度就等于节点个数；而空间复杂度取决于递归的最大深度（每次递归会分配一个栈空间）

*  时间复杂度：O(n)，n为节点个数

*  空间复杂度：O(Height)，Height为树的最大深度

#### 官方版 ####

![4aef12a18e6142468861c8bc3966741f.png][]

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 并更新ans
            return Math.max(L, R) + 1; // 返回该节点为根的子树的深度
        }
    }

**复杂度分析**

*  时间复杂度：O(n)，n为节点个数

*  空间复杂度：O(Height)，Height为树的最大深度

### 总结 ###

这题需要特别注意的是提示中的：“两结点之间的路径长度是以它们之间边的数目表示”，一定要看清楚示例，我刚开始就一直比答案多1，然后看了题解以后才发现问题

[e308c46ae19d43dbb3a8e47355ab63da.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/15eb5fcb5fce429c8d94a2d52501ed3e.png
[4aef12a18e6142468861c8bc3966741f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/0d7b8a0a095d42db9eb7ff8022ec1f7e.png