( “树” 之 DFS) 543. 二叉树的直径 ——【Leetcode每日一题】

怼烎@ 2024-03-23 11:01 35阅读 0赞

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

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

##### 示例 : #####

> 给定二叉树

![在这里插入图片描述][b84d8acf2d75467392c5c04d40b51d12.png]

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

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

#### 思路：DFS ####

> **注意:** 任意两个节点之间的边数都可能是最大直径, 最大的直径不一定包括根节点!

最大值**不一定**包含根节点，**但是一定经过某一个节点**;

**经过该节点** **左右子树的最大高度之和** 即为**最大直径**; 于是，可以使用 **DFS**，求每个节点左右子树的最大高度之和，取出最大值 `maxdia`,即为结果:

*  定义一个全局变量 `maxdia`，用来记录最大直径, 使用 `height(root)` 遍历所有的节点，`height(root)` 的作用是：找出以 `root`为根节点的左右子树的最大高度;
 *  `maxdia` 取值为以经过 `root`为根节点的左右子树的最大高度之和 ,为`left + right`;
 *  以`root` 为左子树或右子树的高度为 `Math.max(left, right) + 1`, 返回给`root`的父节点,;
 *  通过**递归**，找到 `maxdia` 的最大值.

#### 代码：(Java、C++) ####

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

**C++**

/**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
     *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
     *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
     * };
     */
    class Solution {
        
    public:
        int maxdia = 0;
        int diameterOfBinaryTree(TreeNode* root) {
        
            if(root == NULL) return 0;
            height(root);
            return maxdia;
        }
        int height(TreeNode* root){
        
            if(root == NULL) return 0;
            int left = height(root->left);
            int right = height(root->right);
            maxdia = max(maxdia, left + right);
            return 1 + max(left, right);
        }
    };

##### 运行结果： #####

![在这里插入图片描述][a512f6ec72664d6598190c6ade2dffbe.png]

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

*  **时间复杂度**： O ( n ) O(n) O(n)，其中 `n` 为二叉树的节点数，即遍历一棵二叉树的时间复杂度，每个结点只被访问一次。
 *  **空间复杂度**： O ( H e i g h t ) O(Height) O(Height)，其中 `Height` 为二叉树的高度。由于递归函数在递归过程中需要为每一层递归函数分配栈空间，所以这里需要额外的空间且该空间取决于递归的深度，而递归的深度显然为二叉树的高度，并且每次递归调用的函数里又只用了常数个变量，所以所需空间复杂度为  O ( H e i g h t ) O(Height) O(Height)。

题目来源：[力扣。][Link 1]

> 放弃一件事很容易，每天能坚持一件事一定很酷，一起每日一题吧！  
> 关注我 [leetCode专栏][leetCode]，每日更新！

##### 注： 如有不足，欢迎指正！ #####

[b84d8acf2d75467392c5c04d40b51d12.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/6ea83a51fc824d898829a88a802c8560.png
[a512f6ec72664d6598190c6ade2dffbe.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/6812d2d61c984a6cadcc3f80c02abc92.png
[Link 1]: https://leetcode.cn/problems/diameter-of-binary-tree/description/
[leetCode]: http://t.csdn.cn/kQLJO