C++ code and explanation


  • 0
    class Solution {
    public:
    
    
        int maxDepth(TreeNode* root, int depth) {
            while (root) {
                return max(maxDepth(root->left, depth+1), maxDepth(root->right, depth+1));
            }
            return depth;
        }
    
        int diameterOfSubTree(TreeNode* root) {
            if (!root) return 0;
            return maxDepth(root->left, 0) + maxDepth(root->right, 0);
        }
        
        int diameterOfBinaryTree(TreeNode* root) {
            if (!root) return 0;
            // update max of that subtree's "total" diameter
            int maxD = diameterOfSubTree(root);
            maxD = max(maxD, max(diameterOfBinaryTree(root->left),diameterOfBinaryTree(root->right)));
            return maxD;
        }
    };
    

    I thought of this problem as a bunch of smaller problems of the same kind. First, we calculate the max depth of the tree at the root level using diameterOfSubTree. We add up the max depths of that tree's respective left and right children.

    Then we repeat the same process with the root's left and right children--we find the diameter of the root->left's subtree and root->right's subtree, and pick the biggest values out of those three. The recursive call all the way down will return the correct values for the root's left and right children.


Log in to reply
 

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