二叉树的直径(Diameter of Binary Tree)

来源

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/diameter-of-binary-tree

描述

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。

示例 :
给定二叉树
1
/ \
2 3
/ \
4 5
返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。

注意：两结点之间的路径长度是以它们之间边的数目表示。

题解

算法

• 计算当前node左右节点的深度，然后可得到此路径上node的个数 (depth of node.left) + (depth of node.right) + 1
• 搜索每个节点并记录路径上node个数的最大值
• 由于两结点之间的路径长度是以它们之间边的数目表示，故最终结果需将node数 - 1

class Solution {
    int nodeAmount;
    public int diameterOfBinaryTree(TreeNode root) {
        nodeAmount = 1;
        depth(root);
        return nodeAmount - 1;
    }
    public int depth(TreeNode node) {
        if (null == node) return 0;
        int L = depth(node.left);
        int R = depth(node.right);
        nodeAmount = Math.max(nodeAmount, L + R + 1);
        return Math.max(L, R) + 1;
    }
}

复杂度分析

• 时间复杂度：O(N)，每个节点只访问一次。
• 空间复杂度：O(N)，深度优先搜索的栈开销。