C++ ez solution beats 99.80% with explaination


  • 0
    M
    int minDepth(TreeNode* root) {
            if(!root)return 0;
            if(!root->left&&!root->right)return 1; //leaf found, just return 1
    
            //↓current root is not a leaf↓
            int l=-1,r=-1;   //here l and r means min depth to pass through left node and right node, if either node is NULL, just return min depth which pass through the other node
            if(root->left)l=1+minDepth(root->left);
            if(root->right)r=1+minDepth(root->right);
            if(l==-1)return r;
            if(r==-1)return l;
    
            //if both left child and right child exist, return the shorter path
            return min(l,r);
        }
    

  • 0

    @mymax2012gmail.com Your beating 99.8% is actually some fluctuation of the OJ, this kind of case will be removed soon... but indeed your solution is the best solution. But personally I'd prefer the following one which is more readable and cleaner. Anyway, thanks for sharing.

    class Solution {
    public:
        int minDepth(TreeNode* root) 
        {
            if(!root) return 0;
            if(!root->left && !root->right) return 1;
            if(!root->left) return 1+minDepth(root->right);
            if(!root->right) return 1+minDepth(root->left);
            return min(minDepth(root->left), minDepth(root->right))+1;
        }
    };
    

  • 0

    @LHearen Thanks for sharing your solution. This is DFS, right? This kind of recursion solution is always so simple and readable, amazing.


Log in to reply
 

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