【算法题解】50. 二叉树的直径

灰太狼 2024-03-17 15:48 37阅读 0赞

> 这是一道 **简单** 题  
>   
> https://leetcode.cn/problems/diameter-of-binary-tree/

### 题目 ###

给你一棵二叉树的根节点，返回该树的 **直径** 。

二叉树的 **直径** 是指树中任意两个节点之间最长路径的 **长度** 。这条路径可能经过也可能不经过根节点 `root` 。

两节点之间路径的 **长度** 由它们之间边数表示。

**示例 1：**  
![800b8ecebdc5b8e5ac646e9d501b2129.png][]

输入：root = [1,2,3,4,5] 
    输出：3 
    解释：3 ，取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。

**示例 2：**

输入：root = [1,2] 
    输出：1

**提示：**

*  树中节点数目在范围  \[ 1 , 1 0 4 \] \[1, 10^4\] \[1,104\] 内
 *   − 100 < = N o d e . v a l < = 100 -100 <= Node.val <= 100 −100<=Node.val<=100

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

### 题解 ###

二叉树的最大直径有两种种可能：

1.  **左子树的最大深度 + 右子树的最大深度** （左右两边的最长边数 = 左右两边的深度）  
    ![709b53a505610fa6daa8760a3d7ebf59.png][]
2.  **某一棵子树的最大直径**。  
    ![09c078207a2adddaebd4722a7c87a4f7.png][]

所以最终答案应该为上述 `2` 种可能中的最大值，也就是：**以二叉树中的每一个节点为根节点，计算其左右子树的最大深度和，然后取其中的最大值**。

之前解过 [【算法题解】33. 二叉树的最大深度][33.] 这道题目，为了方便查看，我直接将题解中求深度的递归函数粘贴过来并做了简单的调整。

public int depth(TreeNode node) {
        
        if(node == null){
        
            return 0;
        }
    
        int leftDepth = depth(node.left);
        int rightDepth = depth(node.right);
    
        return Math.max(leftDepth, rightDepth) + 1;
    }

因为上述代码片段已经包含了左右子树的最大深度，所以可以同时求得左右子树最大深度之和，命名为 `tempAns`。

又因为最终答案 `ans` 是二叉树中某一个节点为根节点的左右子树最大深度之和，所以我们可以在遍历到每个节点的时候都求一次 `tempAns`，然后取所有 `tempAns` 的最大值即为答案。其中 `ans` 初始值设置为 `0`。

##### Java 代码实现 #####

/**
     * 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 {
        
    
        private int ans = 0;
    
        public int diameterOfBinaryTree(TreeNode root) {
        
    
            depth(root);
    
            return ans;
    
        }
    
        // 求深度
        private int depth(TreeNode node){
        
            if(node == null){
        
                return 0;
            }
            int leftDepth = depth(node.left);
            int rightDepth = depth(node.right);
    
            // 左右子树深度相加
            int tempAns = leftDepth + rightDepth;
    
            // 更新最大值（答案）
            ans = Math.max(tempAns, ans);
    
            return Math.max(leftDepth, rightDepth) + 1;
        }
    }

##### Go 代码实现 #####

/**
     * Definition for a binary tree node.
     * type TreeNode struct {
     *     Val int
     *     Left *TreeNode
     *     Right *TreeNode
     * }
     */
    func diameterOfBinaryTree(root *TreeNode) int {
        
    
        var depth func(node *TreeNode) int
    
        ans := 0
    
        depth = func(node *TreeNode) int {
        
            if node == nil {
        
                return 0
            }
    
            leftDepth := depth(node.Left)
            rightDepth := depth(node.Right)
    
            tempDepth := leftDepth + rightDepth
    
            ans = max(ans, tempDepth)
    
            return max(leftDepth, rightDepth) + 1
    
        }
    
        depth(root)
    
        return ans
    
    }
    
    func max(a int, b int) int {
        
        if a > b {
        
            return a
        }
    
        return b
    }

##### 复杂度分析 #####

**时间复杂度：**  O ( N ) O(N) O(N)，`N` 为二叉树中的节点个数，每个节点都需要遍历一次，时间复杂度为  O ( 1 ) O(1) O(1)，`N` 个节点总计时间复杂度为  O ( N ) O(N) O(N)。

**空间复杂度：**  O ( N ) O(N) O(N)，`N` 为二叉树中的节点个数，空间复杂度主要取决于递归调用栈的深度，最大为 `N`。

[800b8ecebdc5b8e5ac646e9d501b2129.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/e136752c8a0a4e58bf127e69a59aa02b.png
[709b53a505610fa6daa8760a3d7ebf59.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/0c968181986f40fa93834e925e3ff0ca.png
[09c078207a2adddaebd4722a7c87a4f7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/ffbada4baa9044afb041b789caa0ea56.png
[33.]: https://mp.weixin.qq.com/s?__biz=MzU1OTYwMjk1OQ==&mid=2247487549&idx=1&sn=053b9811f47fbbfc6f6f63ecad890bf6&chksm=fc159c5dcb62154bf9889064e18c0af6e62c583bdb7b7ca2edb3516c9812fd404c24ec21b447#rd