Java 1ms solution, bottom up O(N)


  • 0

    For each iteration, if the left node or right node is not balanced, we want to just return false.
    If the left node and right node is balanced, then we need one more step to check the difference between left height and right height, and return True or False accordingly;
    So we can conclude that for each iteration, we need two indicators, we want the height of the left and the right node, we also want to know if the left node and the right node is balanced.
    So, we came up with a question: how to return the two information just using one value aka int value?
    Obviously boolean can not contain the height information, however, int can contain the height value also boolean value, why? we know the height can not be negative, so we set the height to negative to inform that the node is not balanced.
    Here is the code:

    public boolean isBalanced(TreeNode root) {
            if(root==null)
                return true;
            if(getHeight(root)==Integer.MIN_VALUE)
            return false;
            else 
            return true;
        }
    
        public static int getHeight(TreeNode root) {
            if (root == null)
                return 0;
            int leftH = getHeight(root.left);
            int rightH = getHeight(root.right);
            if (leftH == Integer.MIN_VALUE || rightH == Integer.MIN_VALUE)
                return Integer.MIN_VALUE; //you can use any negative number to represent unbalanced 
            if (Math.abs(leftH - rightH) > 1)
                return Integer.MIN_VALUE;
            return Math.max(leftH, rightH) + 1;
        }
    ````>! >! Spoiler

Log in to reply
 

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