当前位置：首页 > article >正文

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

article 2024/9/19 9:09:35

543. 二叉树的直径

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

示例 :

给定二叉树

在这里插入图片描述

返回 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);
    }
};

运行结果：

在这里插入图片描述

复杂度分析：

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