LeetCode //C - 543. Diameter of Binary Tree

543. Diameter of Binary Tree

Given the root of a binary tree, return the length of the diameter of the tree.

The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

The length of a path between two nodes is represented by the number of edges between them.
 

Example 1:

Example 2:

Constraints:

• The number of nodes in the tree is in the range [ 1 , 1 0 4 ] [1, 10^4] [1,104].
• -100 <= Node.val <= 100

From: LeetCode
Link: 543. Diameter of Binary Tree

---

Solution:

Ideas：

1. Recursive Height Calculation: There’s a helper function named height that computes the height of a subtree rooted at a given node. The height of a node is the number of edges on the longest downward path between that node and a leaf. This function is used to find the height of the left and right subtrees for every node in the binary tree.

2. Computing Diameter: The function diameterOfBinaryTree computes the diameter by considering two possibilities for each node:

• The longest path might pass through the node, in which case the length of the path would be the sum of the heights of its left and right subtrees.
• The longest path might not pass through the node, in which case it must lie entirely within either the left subtree or the right subtree.

1. Combining Heights and Diameters: For each node, the function considers the diameter of the left subtree, the diameter of the right subtree, and the longest path through the node (left height + right height). The maximum of these three values gives the diameter at that node.

2. Return Maximum Diameter: The function recursively computes the diameter for every node and returns the maximum value obtained. This maximum value is the diameter of the tree.

Code:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
// Helper function to calculate the height of the binary tree.
int height(struct TreeNode* node) {
    if (node == NULL) {
        return 0;
    }
    int left_height = height(node->left);
    int right_height = height(node->right);
    return (left_height > right_height ? left_height : right_height) + 1;
}

// Main function to calculate the diameter of the binary tree.
int diameterOfBinaryTree(struct TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    
    int left_height = height(root->left);
    int right_height = height(root->right);
    
    int left_diameter = diameterOfBinaryTree(root->left);
    int right_diameter = diameterOfBinaryTree(root->right);
    
    // The diameter at the current node is the sum of the height of left and right subtrees.
    int diameter_at_node = left_height + right_height;
    
    // The largest diameter is the maximum of the left diameter, right diameter, and the diameter at the current node.
    int max_diameter = left_diameter > right_diameter ? left_diameter : right_diameter;
    return max_diameter > diameter_at_node ? max_diameter : diameter_at_node;
}