Java 1ms solution with explanation


  • 6
    M
    public class Solution {
        public boolean isBalanced(TreeNode root) {
            return checkBalance(root) == -1 ? false : true;
        }
        
        // 1. If a subtree is hit as unbalanced, the whole tree is unbalanced. In this case, -1 is set as the return value.
        // 2. If the left subtree and the right subtree of a node are balanced, there are two more cases:
        // 2.1. The tree rooted at the node is unbalanced (the depth of its two subtrees differs by more than 1), as a result, -1 is returned.
        // 2.2 The tree rooted at the node is balanced, then the depth of the tree will be returned.
        public int checkBalance(TreeNode node){
            if (node == null) // case 2.2
                return 0;
                
            int left = checkBalance(node.left);
            if (left == -1) // check case 1
                return -1;
                
            int right = checkBalance(node.right);
            if (right == -1) // check case 1
                return -1;
            
            if (left - right > 1 || right - left > 1)
                return -1; // check case 2.1
            
            return (left > right ? left : right) + 1; // case 2.2
        }
    }

Log in to reply
 

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