【力扣 - 二叉树的直径】

题目描述

给你一棵二叉树的根节点，返回该树的 直径 。
二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。
两节点之间路径的 长度 由它们之间边数表示。

提示：

树中节点数目在范围 [1, 10000] 内

-100 <= Node.val <= 100

题解

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int maxLen(struct TreeNode* root)
{
   
    if(root == NULL)
    {
   
        return 0; // Base case: return 0 if the current node is NULL
    }
    int leftLen;
    int rightLen;
    
    // Calculate the maximum path length of the left subtree
    leftLen = maxLen(root->left) + 1;
    
    // Calculate the maximum path length of the right subtree
    rightLen = maxLen(root->right) + 1;
    
    // Return the maximum of the left and right path lengths
    return leftLen > rightLen ? leftLen : rightLen;
}

int Traversal(struct TreeNode* root)
{
   
    if(root == NULL)
    {
   
        return INT_MIN; // Return minimum integer value if the current node is NULL
    }
    
    int diameter = INT_MIN; // Initialize diameter to minimum integer value
    
    // Calculate the diameter passing through the current node
    diameter = maxLen(root->left) + maxLen(root->right);
    
    // Update diameter with the maximum of diameter, left subtree traversal, and right subtree traversal
    diameter = fmax(diameter, Traversal(root->left));
    diameter = fmax(diameter, Traversal(root->right));
    
    return diameter; // Return the final diameter value
}

int diameterOfBinaryTree(struct TreeNode* root)
{
   
    // Post-order traversal to calculate the diameter of the binary tree
    return Traversal(root);
}