高频编程考题：二叉树的直径（简单）

高频编程考题：二叉树的直径（简单）

引用

CSDN

1.

https://m.blog.csdn.net/LFY5678/article/details/142700067

题目描述

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

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

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

示例 1：

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

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

提示：

• 树中节点数目在范围 [1, 104] 内
• -100 <= Node.val <= 100

解题思路

要找到二叉树的直径，我们需要找到树中任意两个节点之间的最长路径。这个路径的长度由路径中的边数决定，而不是节点数，可以使用深度优先搜索（DFS）的方法：

1. 定义直径 ：直径是树中两个节点之间最长的路径长度。这个路径可能会经过树的根节点，也可能不会。
2. DFS 计算深度 ：

• 使用 DFS 递归遍历树中的每个节点，同时计算每个节点的左右子树的深度；
• 对于每个节点，计算通过该节点的最长路径长度，即左右子树深度之和；
• 更新全局变量 maxDiameter 以记录当前最大直径。

3. 计算节点的深度 ：通过递归计算每个节点的左右子树的深度，返回节点的最大深度。

复杂度分析

时间复杂度

• 计算每个节点的深度 ：对于树中的每个节点，我们都需要递归地计算其左右子树的深度。每个节点的处理（即计算其左右子树深度和更新最大直径）只需要常数时间。
• 总时间复杂度 ：由于每个节点在 DFS 遍历过程中被访问一次，所以时间复杂度是 O(N) ，其中 N 是树中节点的总数。

空间复杂度

• 递归栈的空间 ：由于使用了递归 DFS 方法，递归栈的最大深度等于树的高度。对于最坏情况（例如链式树结构），树的高度可能达到 N（节点数），此时递归栈的空间复杂度为 O(N) 。对于平衡树，递归栈的深度是树的高度，即 O(log N) 。
• 额外空间 ：除了递归栈外，额外使用的空间主要是 maxDiameter 变量，空间复杂度为 O(1) 。

因此，整体的空间复杂度主要由递归栈的深度决定，对于最坏情况下是 O(N) ，而对于平衡树是 O(log N) 。

代码实现

package org.zyf.javabasic.letcode.hot100.tree;
import org.zyf.javabasic.letcode.tree.base.TreeNode;

/**
 * @program: zyfboot-javabasic
 * @description: 二叉树的直径（简单）
 * @author: zhangyanfeng
 * @create: 2024-08-22 11:23
 **/
public class DiameterOfBinaryTreeSolution {
    private int maxDiameter = 0; // 记录最大直径

    public int diameterOfBinaryTree(TreeNode root) {
        calculateDepth(root);
        return maxDiameter;
    }

    // 计算树的深度并更新最大直径
    private int calculateDepth(TreeNode node) {
        if (node == null) {
            return 0;
        }

        // 递归计算左右子树的深度
        int leftDepth = calculateDepth(node.left);
        int rightDepth = calculateDepth(node.right);

        // 更新最大直径
        maxDiameter = Math.max(maxDiameter, leftDepth + rightDepth);

        // 返回当前节点的深度
        return Math.max(leftDepth, rightDepth) + 1;
    }

    public static void main(String[] args) {
        DiameterOfBinaryTreeSolution solution = new DiameterOfBinaryTreeSolution();

        // 示例 1
        TreeNode root1 = new TreeNode(1);
        root1.left = new TreeNode(2);
        root1.right = new TreeNode(3);
        root1.left.left = new TreeNode(4);
        root1.left.right = new TreeNode(5);

        System.out.println("Example 1: " + solution.diameterOfBinaryTree(root1)); // 输出: 3

        // 示例 2
        TreeNode root2 = new TreeNode(1);
        root2.left = new TreeNode(2);

        System.out.println("Example 2: " + solution.diameterOfBinaryTree(root2)); // 输出: 1
    }
}