校招刷题群
高效刷题 迎战校招
校招精选试题
近年面笔经面经群内分享
Java刷题群 前端刷题群 产品运营群
首页 > 数据结构 > 二叉树相关概念
题目

如何计算二叉树内两个节点的最长距离

解答

二叉树中两个节点的最长距离可能有三种情况:

1.左子树的最大深度+右子树的最大深度为二叉树的最长距离
2.左子树中的最长距离即为二叉树的最长距离
3.右子树种的最长距离即为二叉树的最长距离

因此,递归求解即可

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
private static class Result{ 
    int maxDistance; 
    int maxDepth; 
    public Result() { 
    
   
    public Result(int maxDistance, int maxDepth) { 
        this.maxDistance = maxDistance; 
        this.maxDepth = maxDepth; 
    
    int getMaxDistance(TreeNode root){
      return getMaxDistanceResult(root).maxDistance;
    }
    Result getMaxDistanceResult(TreeNode root){
        if(root == null){
            Result empty = new Result(0,-1);
            return empty;
        }
        Result lmd = getMaxDistanceResult(root.left);
        Result rmd = getMaxDistanceResult(root.right);
        Result result = new Result();
        result.maxDepth = Math.max(lmd.maxDepth,rmd.maxDepth) + 1;
        result.maxDistance = Math.max(lmd.maxDepth + rmd.maxDepth,Math.max(lmd.maxDistance,rmd.maxDistance));
        return result;
    }
C 2条回复 评论
秒秒

跟着大佬输出,感觉能量满满

发表于 2023-10-02 21:00:00
0 0
摔伤脚踝的流星

感谢分享!

发表于 2022-02-02 21:00:00
0 0