Two Solutions


  • 0
    L

    // diameter O(n)
    int dfs(TreeNode* root, int& height){
    if(!root) {height = 0; return 0;}
    int lh = 0, rh = 0, ld = dfs(root->left, lh), rd = dfs(root->right, rh);
    height = max(lh, rh)+1;
    return max(lh+rh, max(ld, rd));
    }
    int diameterOfBinaryTree(TreeNode* root) {
    int height = 0;
    return dfs(root, height);
    }

    // O(n^2) solution
    int depth(TreeNode* root){
    return !root ? 0 : max(depth(root->left), depth(root->right)) + 1;
    }
    int diameterOfBinaryTree(TreeNode* root) {
    return !root ? 0 : max(depth(root->left)+depth(root->right), max(diameterOfBinaryTree(root->left), diameterOfBinaryTree(root->right)));
    }


Log in to reply
 

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