本文共 951 字，大约阅读时间需要 3 分钟。

问题解析与解决方案

题目概述

本题要求计算一棵二叉树的直径长度。直径定义为树中最长的节点间路径长度。路径长度是指路径上边的数量，例如根到叶节点的路径长度为2。

解题思路

计算二叉树直径的方法可以通过递归的方式实现。核心思路是比较树中各节点的左子树与右子树的深度之和，取最大值作为当前节点的直径贡献。通过递归计算每个节点的左右子树深度之和，最终得到整个树的直径。

算法性能分析

该方法采用递归的方式遍历整个树，时间复杂度为O(N)，其中N为树的节点数。这种方法避免了多次遍历树，确保了高效性。这种方法的时间复杂度为O(N)，空间复杂度为O(1)，适用于大规模树结构。

解决方案实现

以下是实现代码：

class Solution {
    public int depth(TreeNode root, int &ans) {
        if (root == null) {
            return 0;
        }
        int leftDep = 0;
        int rightDep = 0;
        if (root.left != null) {
            leftDep = 1 + depth(root.left, ans);
        }
        if (root.right != null) {
            rightDep = 1 + depth(root.right, ans);
        }
        ans = Math.max(leftDep + rightDep, ans);
        return Math.max(leftDep, rightDep);
    }
    public int diameterOfBinaryTree(TreeNode root) {
        int maxDepth = 0;
        depth(root, maxDepth);
        return maxDepth;
    }
}

该代码通过递归计算每个节点的左、右子树的深度之和，更新全局最大值。返回的结果即为树的直径长度。

转载地址：http://zzaq.baihongyu.com/