JAVA solution with recursion --other better solution?


  • 2
    Y
    public class Solution {
    public boolean isBalanced(TreeNode root) {
        
        if (root==null) return true;
        if (root.left==null && root.right==null) return true;
        
        if (Math.abs(countDepth(root.left) - countDepth(root.right))>1) return false;
        
        return (isBalanced(root.left) && isBalanced(root.right));
            
    }
    
    
    
    public int countDepth(TreeNode r){
        if (r==null) return 0;
        if (r.left==null && r.right==null) return 1;
        return 1+Math.max(countDepth(r.left), countDepth(r.right));
        
        
    }
    

    }


  • 0
    X
    public class Solution {
    public boolean isBalanced(TreeNode root) {
        Object isBanlance = height(root);
        if(isBanlance.equals(false))
            return false;
        return true;
    }
    
    public Object height(TreeNode node)
    {
        if(node == null)
            return 0;
        if(node.left == null && node.right == null)
            return 1;
        Object leftH = height(node.left);
        if(leftH.equals(false))
            return false;
        Object rightH = height(node.right);
        if(rightH.equals(false))
            return false;
        int lefth = Integer.valueOf(leftH.toString());
        int righth = Integer.valueOf(rightH.toString());
        if(Math.abs(lefth - righth) > 1)
            return false;
        return 1 + (lefth > righth ? lefth : righth);
    }
    

    }

    I think it can stop right now when the find the node is not height-balance other than visits all the node some times,right?


  • 4
    Y
    public class Solution {
        public boolean isBalanced(TreeNode root) {
           if (depthJudge(root) == -1) {
               return false;
           }
           else {
               return true;
           }
        }
        
         public int depthJudge(TreeNode root) {
            if (root == null) {
                return 0;
            }
            int ldepth = depthJudge(root.left);
            int rdepth = depthJudge(root.right);
            
            if (ldepth == -1 || rdepth == -1 || Math.abs(ldepth - rdepth) > 1) {
                return -1;
            }
            else {
                return 1 + Math.max(ldepth, rdepth);
            }
        }
    }
    

    depth calculation and determining whether the tree is height-balanced or not could finish in one recursive loop.


  • 3
    X
    public class Solution {
        public boolean isBalanced(TreeNode root) {
    		if(root == null)
    		{
    		    	return true;
    		}
    		else 
    		{
    			    if(!isBalanced(root.left) || !isBalanced(root.right))
    			    {
    					return false;
    			    }
    			    else
    			    {
    					int leftDepth = root.left==null?0:root.left.val;
    					int rightDepth = root.right==null?0:root.right.val;
    					if(Math.abs(leftDepth - rightDepth) <= 1)
    					{
    					    root.val = 1 + Math.max(leftDepth, rightDepth);
    					    return true;
    					}
    			    }
    			    return false;
    		}
        }
    

    }

    Single method solution at the cost of changing the value in the nodes (using val to hold the depth). Probably not acceptable in real life but good enough for the OJ.


  • 0
    N

    better than i


  • 0
    N
    if (r.left==null && r.right==null) return 1;
    

    I do not think the sentence is needed.


  • 0
    J

    This solution is so smart!


Log in to reply
 

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