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

LeetCode100之二叉树的直径(543)--Java

article 2025/3/12 11:39:07

1.问题描述

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

二叉树的直径是指树中任意两个节点之间最长路径的长度。这条路径可能经过也可能不经过根节点 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

难度等级

简单

题目链接

二叉树的直径

2.解题思路

这道题目是要求二叉树的直径，这道题如果搞清楚了各个概念直接的关系，就会变得非常简单，我们一起来看一下。

首先，我们要求的是二叉树的直径，根据题目给的定义，二叉树的直径是二叉树中任意两个节点之间最大路径的长度。所以我们的问题就是找到最大的路径长度，而路径长度=经过的节点数-1。所以，我们可以把问题转化为求经过最多的节点数。

我们要求经过最多的节点数，怎么样才能经过尽可能多的节点数呢？那肯定要最深的节点一直到根节点再转向，转向到另外一棵子树的最深节点处。但是这里有一个问题，就是到根节点转向，不一定就是最多的节点数，可能另外一棵子树没有多少节点呢？反而可能是在某一个节点转向之后，节点数更多。所以，我们的解决办法就是求出以每一个节点为根节点，从左最深处到右最深处的节点数，然后取最大值。

这里要明确一点，要从左最深处到右最深处，那我们就要分别求出左右两颗子树的深度。那这个问题就被转化为求最大深度的问题了。

我们定义一个变量，用来更新最大节点数。

    //存储经过的最大节点数
    int result = 1;

递归的结束条件是，如果节点为空，直接返回0就可以了。

        //空节点返回0
        if(node == null){
            return 0;
        }

然后我们就可以对左右子树递归求深度，然后取左右子树的最大值+1(这里的+1指加上当前根节点本身)进行返回。

        //左子树的深度
        int L = dfs(node.left);
        //右子树的深度
        int R = dfs(node.right);
        .....
        return Math.max(L,R) + 1;

到这里，我们已经完成了求最大深度的逻辑。但是我们还缺少了求最大节点数的逻辑。到这一步，已经不难了，因为我们前面已经递归求了左右子树的深度，我们只需要将左子树的深度加上右子树的深度，再加1，就是以当前节点为根，所可能经过的最大节点数了。这里的+1(是因为要从左最深到右最深，必须经过当前节点，所以要把当前节点也算上)。将以当前节点为根所经过的最大节点数与全局已经记录的最大节点数进行比较，取最大值即可。

        //更新经过的最大节点数
        result = Math.max(result,L + R + 1);

当我们求完整个树的深度时，我们的最大节点数也就跟着求出来了。此时，只需要按照定义，将经过的最大节点数-1返回即可。

        dfs(root);
        //直径=经过的最大节点数-1
        return result - 1;

3.代码展示

/**
 * 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 {
    int result = 1;
    public int diameterOfBinaryTree(TreeNode root) {
        dfs(root);
        //直径=经过的最大节点数-1
        return result - 1;
    }
    public int dfs(TreeNode node){
        //空节点返回0
        if(node == null){
            return 0;
        }
        //左子树的深度
        int L = dfs(node.left);
        //右子树的深度
        int R = dfs(node.right);
        //更新经过的最大节点数
        result = Math.max(result,L + R + 1);
        return Math.max(L,R) + 1;
    }
}