📝 题目描述

题目链接：二叉树的直径

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

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

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

示例：

示例 1：

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

示例 2：

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

提示：

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

💡 解题思路

方法一：深度优先搜索

本质上还是后序遍历的思想。

一条路径的长度为该路径经过的节点数减一，所以求直径（即求路径长度的最大值）等效于求路径经过节点数的最大值减一。

求直径−>求节点求直径 -> 求节点

而任意一条路径均可以被看作由某个节点为起点，从其左儿子和右儿子向下遍历的路径拼接得到。

假设我们知道对于该节点的左儿子向下遍历经过最多的节点数 L （即以左儿子为根的子树的深度） 和其右儿子向下遍历经过最多的节点数 R （即以右儿子为根的子树的深度），那么以该节点为起点的路径经过节点数的最大值即为 L+R+1 。

求节点−>求深度求节点 -> 求深度

综上所述，我们在求根节点的深度时，不可避免的会遍历到所有节点，因此我们可以顺便记录一下我们遇到的“如果以当前节点作为路径的最高点，直径是多少（即当前节点的左深度 + 右深度）”。

🔧 代码实现

1、深度优先搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * 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 max_diameter = 0; // 用于记录全局最大直径
    int diameterOfBinaryTree(TreeNode* root) {
        checkDepth(root);
        return max_diameter; // 返回遍历过程中记录的最大值
    }
    // 其实就是求深度
    int checkDepth(TreeNode* node) {
        if (!node) return 0;
        
        // 递归计算左右子树的深度
        int leftdepth = checkDepth(node->left);
        int rightdepth = checkDepth(node->right);

        // 在遍历每个节点时，都计算一下穿过该节点的局部直径，并更新全局最大值
        max_diameter = max(max_diameter, leftdepth + rightdepth);

        // 返回该节点的最大深度
        return max(leftdepth, rightdepth) + 1;
    }
};

📊 复杂度分析

1、深度优先搜索

  • 时间复杂度：O(N)O(N)，其中 N 为二叉树的节点数。每个节点都会被访问且只被访问一次。
  • 空间复杂度：O(H)O(H)，其中 H 为二叉树的高度。这主要是递归调用栈的开销（最坏情况下退化为链表是 O(N)O(N)，平衡树是 O(logN)）O(logN)）。

🎯 总结

  • 核心思想：转换的思想很重要，将求直径转换为求深度。