543. 二叉树的直径#

public class Solution {
    // 全局变量：记录遍历过程中发现的最大直径（按边数计算）
    private int maxDiameter = 0;

    public int diameterOfBinaryTree(TreeNode root) {
        // 一次 DFS：在计算每个节点深度的同时更新最大直径
        calculateDepth(root);

        // 返回最大直径（边的条数，不是节点个数）
        return maxDiameter;
    }

    private int calculateDepth(TreeNode node) {
        // 递归终止条件：空节点深度为 0
        if (node == null) return 0;

        // 递归获取左子树深度（节点数）
        int leftDepth = calculateDepth(node.left);
        // 递归获取右子树深度（节点数）
        int rightDepth = calculateDepth(node.right);

        // 经过当前节点的路径长度（边数）= 左深度 + 右深度
        // 与历史最大值比较并更新全局答案
        maxDiameter = Math.max(maxDiameter, leftDepth + rightDepth);

        // 返回当前节点向下的最大深度：取左右较大者并加上当前节点
        return Math.max(leftDepth, rightDepth) + 1;
    }
}

public int diameterOfBinaryTree(TreeNode root) {
    // 空树没有路径，直径为 0
    if (root == null) return 0;

    // 记录当前已知最大直径
    int maxDiameter = 0;
    // 节点栈：用于手动遍历整棵树
    Stack<TreeNode> nodeStack = new Stack<>();
    // 深度栈：与节点栈一一对应，保存节点所在深度（此实现中主要用于同步遍历状态）
    Stack<Integer> depthStack = new Stack<>();

    // 根节点入栈，深度记为 0
    nodeStack.push(root);
    depthStack.push(0);

    // 遍历所有节点，尝试把每个节点当作“直径拐点”
    while (!nodeStack.isEmpty()) {
        // 弹出当前节点及其深度信息
        TreeNode node = nodeStack.pop();
        int currentDepth = depthStack.pop();

        // 计算左子树深度（为空则记 0）
        int leftDepth = node.left != null ? 
            getNodeDepth(node.left) : 0;
        // 计算右子树深度（为空则记 0）
        int rightDepth = node.right != null ? 
            getNodeDepth(node.right) : 0;

        // 用“左深度 + 右深度”更新最大直径
        maxDiameter = Math.max(maxDiameter, leftDepth + rightDepth);

        // 右子节点存在则入栈，待后续继续计算
        if (node.right != null) {
            nodeStack.push(node.right);
            depthStack.push(currentDepth + 1);
        }

        // 左子节点存在则入栈，待后续继续计算
        if (node.left != null) {
            nodeStack.push(node.left);
            depthStack.push(currentDepth + 1);
        }
    }

    // 返回遍历结束后得到的最大直径
    return maxDiameter;
}

// 辅助方法：获取节点深度
private int getNodeDepth(TreeNode node) {
    // 空节点深度为 0
    if (node == null) return 0;
    // 当前节点深度 = 1 + max(左深度, 右深度)
    return 1 + Math.max(
        getNodeDepth(node.left), 
        getNodeDepth(node.right)
    );
}