543. Diameter of Binary Tree

[jason89521]

Practice Dates

• 2024/05/16

Description

Link: https://leetcode.com/problems/diameter-of-binary-tree/description/

Solution

In this problem, we can use in-order traversal to solve it. For each root node in the recursive function, we assume that it must be one of the nodes in the diameter. Then, we add the longest path from the left node and the longest path from the right node. Finally, we return the largest value among the sum, the diameter which assumes the left child is the root node, and the diameter which assumes the right child is the root node.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int diameterOfBinaryTree(TreeNode* root) {
        return recursive(root).second;
    }

    std::pair<int, int> recursive(TreeNode* root) {
        if (root == nullptr) {
            return {0, 0};
        }
        auto left = root->left, right = root->right;
        if (left == nullptr && right == nullptr) {
            return {0, 0};
        }

        auto leftPair = recursive(left), rightPair = recursive(right);
        auto leftPath = left == nullptr ? 0 : leftPair.first + 1;
        auto rightPath = right == nullptr ? 0 : rightPair.first + 1;
        auto leftMax = leftPair.second, rightMax = rightPair.second;

        auto longestPath = std::max(leftPath, rightPath);
        auto max = std::max( std::max(leftMax, rightMax), leftPath + rightPath );

        return {longestPath, max};

    }
};

Performance

Time complexity:

[jason89521]

Instead of returning a pair, we can pass an integer reference to record the largest diameter.