Skip to content

543 Diameter of Binary Tree

Given a binary tree, you need to compute 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.

Example: Given a binary tree

          1
         / \
        2   3
       / \
      4   5

Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].

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

Idea:

Recursion

alt

Solution 1:

class Solution {
public:
    int diameterOfBinaryTree(TreeNode* root) {
        ans_ = 0;
        LP(root);
        return ans_;
    }
private:
    int ans_;
    int LP(TreeNode* root) {
        if (!root) return -1;
        int l = LP(root->left) + 1;
        int r = LP(root->right) + 1;
        ans_ = max(ans_, l + r);
        return max(l, r);
    }
};

Solution 2: passed 101/106 TLE - Floyd-Warshall

// State: 101/106 passed TLE
class Solution {
public:
    int diameterOfBinaryTree(TreeNode* root) {
        if (!root) return 0;
        edges_.clear();
        int n = 0;
        buildGraph(root, n, -1);
        vector<vector<int>> d(n, vector<int>(n, n));
        for (int i = 0; i < n; ++i) d[i][i] = 0;
        for (const auto& pair : edges_)
            d[pair.first][pair.second] = 1;

        for (int k = 0; k < n; ++k)
            for (int i = 0; i < n; ++i)
                for (int j = 0; j < n; ++j)
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

        int ans = INT_MIN;
        for (int i = 0; i < n; ++i)
                for (int j = 0; j < n; ++j) {
                    if (d[i][j] == n) continue;
                    ans = max(ans, d[i][j]);
                }
        return ans;
    }

private:
    void buildGraph(TreeNode* node, int& id, int pid) {
        if (!node) return;
        int node_id = id++;
        if (pid >= 0) {
            edges_.emplace_back(node_id, pid);
            edges_.emplace_back(pid, node_id);
        }
        buildGraph(node->left, id, node_id);
        buildGraph(node->right, id, node_id);
    }
    vector<pair<int,int>> edges_;
};

Solution 3:

Simulate recursion with a stack. We also need to track the return value of each node.

// Runtime: 15 ms
class Solution {
public:
    int diameterOfBinaryTree(TreeNode* root) {
        if (!root) return 0;
        int ans = 0;
        unordered_map<TreeNode*, int> d{{nullptr, -1}};
        stack<TreeNode*> s;
        s.push(root);
        while (!s.empty()) {
            TreeNode* node = s.top();
            if (d.count(node->left) && d.count(node->right)) {
                int l = d[node->left] + 1;
                int r = d[node->right] + 1;
                ans = max(ans, l + r);
                d[node] = max(l, r);
                // children's results will never be used again, safe to delete here.
                if (node->left) d.erase(node->left);
                if (node->right) d.erase(node->right);
                s.pop();
            } else {
                if (node->left) s.push(node->left);
                if (node->right) s.push(node->right);
            }
        }
        return ans;
    }
};
    1. Longest Univalue Path
    1. Network Delay Time