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


  • 64
    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

    Great idea! I can understand that this avoid unnecessary repeated work. But can someone please tell me that, does this idea apply any concept in DFS? It seems like DFS to me, for it runs recursively till it hits the leaf node. But it is a little weird that it doesn't use Stack... from my concept DFS is something that must associate with Stack, isn't it?

    Please correct me if I'm wrong, thanks!


  • 0
    A

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


Log in to reply
 

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