Tle on minimum depth of binary tree


  • 0
    C
        public static int maxDepth(TreeNode root) {
            int maximum= 0;
            if(root == null)
    {
                return 0;
    }
            maximum= maxDepth(root.left) > maxDepth(root.right) ? maxDepth(root.left) : maxDepth(root.right);
            return maximum + 1;
        }

  • 0
    V

    TLE is caused to wrong recursion. The values of maxDepth(root.left) and maxDepth(root.right) must be stored in variables for checking the boolean condition of which one is greater.

    class Solution {
    private:
        int min_depth = 10000;
    public:
        void minHelper(TreeNode *root, int depth)
        {
            if(depth >= (min_depth))
                return;
            if(root->left == NULL && root->right==NULL)
            {
                min_depth = depth+1;
                return;
            }
            if(root->left)
                minHelper(root->left, depth+1);
            if(root->right)
                minHelper(root->right, depth+1);
        }
    
        int minDepth(TreeNode *root) {
             if(root == NULL)
                return 0;
            minHelper(root, 0);
            return min_depth;
        }
    };

Log in to reply
 

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