Java 1ms Solution


  • 12
    B

    This is perhaps a bit hacky but, hey, it works!

    private int helper(TreeNode root, int height)
    {
        if (root == null)
        {
            return height;
        }
        
        int leftTree = helper(root.left, height + 1);
        int rightTree = helper(root.right, height + 1);
        if (leftTree < 0 || rightTree < 0 || Math.abs(leftTree - rightTree) > 1)
        {
            return -1;
        }
        
        return Math.max(leftTree, rightTree);
    }
    
    public boolean isBalanced(TreeNode root) {
        return helper(root, 0) >= 0;
    }
    

    I tried to avoid mutual recursion or having two functions that both recurse. Having two functions that both recurse, one to get the depth of the left and right subtree, and one to continue down the tree if that node checks out, works fine but can recurse an unnecessary number of times if the tree is valid. This function will always complete in O(nodes) since it just calculates the max depth of each subtree and when the recursion unwinds it checks to see if the restriction on the height has been broken. If it has, it sets the height to -1 (hacky), indicating that the restrictions has been broken. Essentially, this just gets around returning two values, one for whether the restriction has been broken and one for the max height of tree.


Log in to reply
 

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