C++ Recursive O(N) Time O(1) Space


  • 0
    M
    class Solution {
    public:
        pair<int, int> HalfAndFull(TreeNode const * root) {
            if (!root) return {0, 0};
            auto l = HalfAndFull(root->left), r = HalfAndFull(root->right);
            return {1 + max(l.first, r.first), max(1 + l.first + r.first, max(l.second, r.second))};
        }
        int diameterOfBinaryTree(TreeNode* root) {
            return max(0, HalfAndFull(root).second - 1);
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.