Java simple O(n) Solution


  • 2
    L

    The basic idea of this program is to recursively compute the height of the left subtree and of the right subtree. If the returned two heights' are both positive and their difference is less or equal to 1, return the larger height. Otherwise, return -1 which indicates there existing heights' differ than 1.

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public boolean isBalanced(TreeNode root) {
            return compareHeight(root,0)>=0;
        }
        
        public int compareHeight(TreeNode node, int h)
        {
            if(node==null) return h;
            int left_h = compareHeight(node.left,h+1);
            int right_h = compareHeight(node.right,h+1);
            
            return (left_h>=0 && right_h>=0 && Math.abs(left_h-right_h)<=1)?Math.max(left_h,right_h):-1;
        }
    }

  • 0
    H

    Good solution. Thanks for sharing!


Log in to reply
 

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