543 二叉树的直径

一、题目

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

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

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

二、题解

2.1 深度优先搜索

思路： 任意一条路径都可以看作以某个节点为「拐点」，由它向左、右子树各延伸一条最长链拼成。定义 depth(node) 返回以 node 为根的子树最大深度（节点数）：递归求出左右子树深度 L、R，则经过该节点的最长路径节点数为 L + R + 1，用它更新全局最大值 ans；而向上返回的深度只能取单边，即 max(L, R) + 1。直径按边数计，故最终答案为 ans - 1。

/**
 * 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 {
    // ans 记录以某个节点为根时，最长路径上的节点个数
    // 最终直径 = 节点数 - 1（因为直径是边的数量）
    int ans;

    public int diameterOfBinaryTree(TreeNode root) {
        // 初始化 ans 为 1（至少包含当前节点自身）
        ans = 1;

        // 从根节点开始递归计算深度
        // 在递归过程中，ans 会被更新为最大路径节点数
        depth(root);

        // 返回直径（边数）= 最大节点数 - 1
        // 例如 3 个节点的路径，只有 2 条边
        return ans - 1;
    }

    /**
     * 计算以 node 为根的子树的最大深度（高度）
     * 同时更新全局变量 ans：经过当前节点的最长路径节点数
     */
    public int depth(TreeNode node) {
        // 递归终止：空节点的深度为 0
        if (node == null) {
            return 0;
        }

        // 递归计算左子树的最大深度
        // L 表示从当前节点向左子树延伸的最长链的节点数
        int L = depth(node.left);

        // 递归计算右子树的最大深度
        // R 表示从当前节点向右子树延伸的最长链的节点数
        int R = depth(node.right);

        // 关键：更新全局最大直径
        // 经过当前节点的最长路径 = 左子树深度 + 右子树深度 + 当前节点自身
        // 即 L + R + 1（节点数）
        ans = Math.max(ans, L + R + 1);

        // 返回当前节点的深度，供上层使用
        // 当前节点的深度 = max(左子树深度, 右子树深度) + 1（加上当前节点）
        // 注意：返回的是单边最大深度，不是两边之和（那是直径）
        return Math.max(L, R) + 1;
    }
}

时间复杂度：O(n)O(n)

空间复杂度：O(h)O(h)

评论