Java solution based on height, check left and right node in every recursion to avoid further useless search


  • 65
    M
    public boolean isBalanced(TreeNode root) {
        if(root==null){
            return true;
        }
        return height(root)!=-1;
        
    }
    public int height(TreeNode node){
        if(node==null){
            return 0;
        }
        int lH=height(node.left);
        if(lH==-1){
            return -1;
        }
        int rH=height(node.right);
        if(rH==-1){
            return -1;
        }
        if(lH-rH<-1 || lH-rH>1){
            return -1;
        }
        return Math.max(lH,rH)+1;
    }

  • 29
    A

    Great code, but the first

     if(root==null){
            return true;
        }
    

    is unnecessary because it will be checked within the height function.


  • 0
    Z
    This post is deleted!

  • 0
    Y

    Great! Much better than my answer which cost O(N2)...


  • 8
    E

    My code is more concise

        /**
     * 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 getDepth(root)!=-1;
        }
        
        public int getDepth(TreeNode root){
            if(root==null){
                return 0;
            }
            int left = getDepth(root.left);
            if(left!=-1){
                int right = getDepth(root.right);
                if(right!=-1){
                    return Math.abs(left-right)<=1?1+Math.max(left,right):-1;
                }
            }
            return -1;
        }
    }
    

  • 2
    This post is deleted!

  • 4

    Good idea using -1 as unbalanced signal alternatively you could use a reference parameter or pointer or whatever you language offers. Here's a C# version

        public bool IsBalanced(TreeNode root) 
        {
            bool result = true;
            int depth = Depth(root, ref result);
            return result;
        }
        
        public int Depth(TreeNode node, ref bool result)
        {
            if (result == false || node == null) return 0;
            int leftDepth = Depth(node.left, ref result);
            int rightDepth = Depth(node.right, ref result);
            
            if (leftDepth - rightDepth > 1 || leftDepth - rightDepth < -1)
            {
                result = false;
            }
            
            return 1 + Math.Max(leftDepth, rightDepth);
        }
    

  • 0

    good solution using -1 as a boolean marker!


  • 0
    Y

    Hey @mingyuan, your solution is really elegant. However, I am not able to understand why my solution's logic is incorrect. Do you have any idea? Here is the code:

    public class Solution {
        public boolean isBalanced(TreeNode root) {
            if(root==null) return true;
             return     Math.abs(h(root.left) - h(root.right))<=1 ; 
            
        }
        
        public int h(TreeNode root){
            if(root==null) return 0;
            return (1 + Math.max(h(root.left),h(root.right)));
        }
    }
    

  • 0
    T
    This post is deleted!

  • 0

    @yash.shrivastav25 said in Java solution based on height, check left and right node in every recursion to avoid further useless search:

    return Math.abs(h(root.left) - h(root.right))<=1 && isBalanced(root.left) && isBalacend(root.right)


  • 0
    E
    public class Solution {
        
        boolean flag;
        public boolean isBalanced(TreeNode root) {
            flag = true;
            judge(root);
            return flag;
        }
        
        public int judge(TreeNode tNode){
            if(tNode == null) return 0;
            int leftLen = 1 + judge(tNode.left);
            int rightLen = 1 + judge(tNode.right);
            if(Math.abs(rightLen - leftLen) > 1){
                flag = false;
                return -1;
            } 
            return leftLen > rightLen ? leftLen : rightLen;
        }
    }
    

  • 0
    A

    @Eva001 why are you returning -1 after setting flag to false


  • 0
    A

    @jdrogin why have you taken result == false in first statement of depth


  • 0
    S
    This post is deleted!

  • 0
    A

    @abhinav_smart
    I guess here -1 is a boolean marker, since the types of return value of two functions are different.


  • 0
    F

    @mingyuan It seems be AVL tree algorithm. Here is my code which runs more time, because it caculates repeatedly.

    class Solution {
        public boolean isBalanced(TreeNode root) {
            if(root == null) return true;
            if(root.left == null && root.right == null) return true;
            return Math.abs(maxDepth(root.left) - maxDepth(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
        }
        public int maxDepth(TreeNode node){
            if(node == null) return 0;
            return 1 + Math.max(maxDepth(node.left), maxDepth(node.right));
        }
    }
    

Log in to reply
 

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