C++ 7-line, without finding depth in a separate func


  • 0
    E

    I found many solutions which had separate function for finding depth. In that case there are extra DFS iterations.
    The idea in my solution is simple, to find depth and diameter together, and save multiple traversals.
    I like writing self-explanatory code. :)
    Please go through code-comments for full understanding.

    class Solution {
    public:
        int diameterOfBinaryTree(TreeNode* root) {
            return diameterAndDepth(root)[0];
        }
        // given a TreeNode, return vector of size 2
        // index 0 has diameter
        // index 1 has depth of the subtree
        vector<int> diameterAndDepth(TreeNode* root) {     
            if( root==NULL ) return {0, 0};
    
            vector<int> leftN = diameterAndDepth(root->left);
            vector<int> rightN = diameterAndDepth(root->right);
    
            // calculating diameter by finding max of
            // 1. diameter of left child, given by leftN[0]
            // 2. diameter of right child, given by rightN[0]
            // 3. diameter passing through root, given by sum of depths of left child( leftN[1] ) and right child( rightN[1] )
            int diam = max( max(leftN[0], rightN[0]),  leftN[1]+rightN[1]);
    
            // depth is given by max of depths of its children + 1
            return { diam, max(leftN[1], rightN[1])+1 };
        }
    

Log in to reply
 

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