543. Diameter of Binary Tree

1. Description

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.

2. Example

Example 1

Input: root = [1,2,3,4,5]
Output: 3
Explanation: 3 is the length of the path [4,2,1,3] or [5,2,1,3].

Example 2

Input: root = [1,2]
Output: 1

3. Constraints

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

4. Solutions

Depth-First Search

n is the number of nodes in root
Time complexity: O(n)
Space complexity: O(logn)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
public:
    int diameterOfBinaryTree(TreeNode *root) {
        find_max_diameter(root);
        return diameter_;
    }

    int find_max_diameter(TreeNode *root) {
        if (root == nullptr) {
            return 0;
        }

        int left_depth = find_max_diameter(root->left);
        int right_depth = find_max_diameter(root->right);

        diameter_ = max(diameter_, left_depth + right_depth);

        return 1 + max(left_depth, right_depth);
    }

private:
    int diameter_ = 0;
};