Can we have a better solution


  • 15
    H

    My solution for this problem is as follows:

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

    }

    But it has two recursions, one for depth() and one for isBalanced(). Will there be a performance issue?


  • 0
    J
    public class Solution {
    
    int height(TreeNode root) {
        if(root==null) return 0;
        int lh=height(root.left);
        int rh=height(root.right);
        return 1+(lh>rh ?lh :rh);
    }
    public boolean isBalanced(TreeNode root) {
        if(root==null) return true;
        int lh=height(root.left);
        int rh=height(root.right);
        
        return (rh>lh ?(1>=(rh-lh)) :(1>=(lh-rh))) && isBalanced(root.left) && isBalanced(root.right);
        
    }}

  • 0
    L

    This is the way to avoid 2 recursive method calls. The idea is exactly same as 2 above.

    public class Solution
    {
    	public boolean isBalanced(TreeNode root)
    	{
    		if (root == null)
    			return true;
    		
    		int[] num = new int[1];
    		num[0] = 0;
    		
    		checkHeight(root, num);
    		
    		return num[0] == 0;
    	}
    	
    	private int checkHeight(TreeNode p, int[] num)
    	{
    		if (num[0] == 1)
    			return 0;
    		
    		if (p.left == null && p.right == null)
    		{
    			return 1;
    		}
    		
    		int leftDepth = 1;
    		if (p.left != null)
    			leftDepth = checkHeight(p.left, num) + 1;
    
    		
    		int rightDepth = 1;
    		if (p.right != null)
    			rightDepth = checkHeight(p.right, num) + 1;
    		
    		
    		if ( Math.abs(rightDepth - leftDepth) > 1)
    		{
    			num[0] = 1;
    		}
    		
    		return Math.max(leftDepth, rightDepth);
    	}
    }

  • 0
    J

    How does this prevent two recursions? To me it seems like your recurse once for height and once for isBalanced on each node?


  • 18
    J

    I use a function that checks for balance while getting height. Also "short-circuit" once an imbalance is found:

    bool isBalanced(TreeNode *root) {
        bool global_is_balanced = true;
        isBalancedAux(root, global_is_balanced);
        return global_is_balanced;
    }
    
    int isBalancedAux(TreeNode *root, bool& is_balanced) {
        if (root == NULL) return 0;
        if (is_balanced == false) return 0;
        
        int lh = isBalancedAux(root->left, is_balanced);
        int rh = isBalancedAux(root->right, is_balanced);
        
        // prevent overwrite of is_balanced
        if (is_balanced == false) return 0;
    
        is_balanced = abs(lh-rh) <= 1;
        return max(lh, rh) + 1;
    }

  • 33
    S

    Hey the flame of heaven,

    I had the same confusion in my sophomore year when I tried to write the balanced checking function. And I figured out after some exercise that:

    "In order to be away from the scenario of recursion in recursion, the only way is to think about adding a variable so that one recursive process can perform two functionalities at the same time."

    Back to this problem, it is clear after thinking for a while that you definitely need to check the height, which is unavoidable. So the next thought process would be how can you check the balance while recursively computing for the height. And the solution will be straightforward. In most cases, the variable that indicates the result would be passed by reference.

    Here is my solution

    class Solution {
    public:
        int ifBalanced_helper(TreeNode* root, bool& result){
            if(!root) return 0;
            int leftHeight = ifBalanced_helper(root->left, result);
            int rightHeight = ifBalanced_helper(root->right, result);
            if(abs(leftHeight-rightHeight)>1) result = false;
            return max(leftHeight, rightHeight)+1;
        }
    
        bool isBalanced(TreeNode *root) {
            bool result = true;
            ifBalanced_helper(root, result);
            return result;
        }
    };

  • 5
    U

    Similar to John6's answer, we should stop tree traversal as soon as it is found to be unbalanced. Instead of use a Boolean variable, the returned height itself can be used to indicate that.

    class Solution:
    # @param root, a tree node
    # @return a boolean
    def isBalanced(self, root):
        return self.getHeight(root) is not None
    
    def getHeight(self, root):
        if not root:
            return 0
        lh = self.getHeight(root.left)
        if lh is None:
            return None
        rh = self.getHeight(root.right)
        if rh is None:
            return None
        if abs(lh-rh) > 1:
            return None
        else:
            return max(lh,rh)+1

  • 3
    Z
    bool isBalanced(TreeNode *root) {
        if(root == nullptr) return true;
        return (helper(root) == -1? false:true);
    }
    
    int helper(TreeNode *root) {
        int left_height = 0, right_height = 0;
        if(root->left != nullptr){
            left_height = helper(root->left);
        }
        
        if(root->right != nullptr){
            right_height = helper(root->right);
        }
        
        if(left_height == -1 || right_height == -1) return -1;
        
        if(abs(left_height - right_height) > 1) return -1;
        
        return (left_height > right_height? left_height:right_height) + 1;
    }
    

    return -1 if this subtree is unbalanced and return the height if it is balanced.


  • -1
    Z

    Single Recursion and easy understandable code -

    class Solution {
    public:
        int rec(TreeNode *root){
            if(root == NULL)
                return 0;
            
            int l = 1 + rec(root->left);
            int r = 1 + rec(root->right);
            
            if(abs(l-r) > 1)
                return (1<<30);
            return max(l,r);
        }
        
        bool isBalanced(TreeNode *root) {
            if(rec(root) >= (1<<30))
                return false;
            return true;
        }
    };

  • 11
    G

    i use the Maximum Depth of Binary Tree code and change a bit,solve the problem with Single Recursion

    public class Solution {
    public boolean isBalanced=true;
    
    public boolean isBalanced(TreeNode root) {
        maxDepth(root);
        return isBalanced;
    }
    
    public int maxDepth(TreeNode root) {
       if(root==null)
         return 0;
       else{
           int leftDepth=maxDepth(root.left)+1;
           int rightDepth=maxDepth(root.right)+1;
           if(Math.abs(leftDepth-rightDepth)>1)
                isBalanced=false;
           return leftDepth>rightDepth?(leftDepth):(rightDepth);
       }
    }
    

    }


  • 0
    B
    This post is deleted!

  • 3
    S
    public class Solution {
    public boolean isBalanced(TreeNode root) {
        return balanceHelper(root) > -1;
    }
    public int balanceHelper(TreeNode root)  {
        if(root == null)  return 0;
        int left = balanceHelper(root.left);
        if(left == -1)  return -1;
        int right = balanceHelper(root.right);
        return (right == -1 || Math.abs(left - right) > 1) ? -1 : Math.max(left, right) + 1;
    }
    

    }

    Clearly we need to track both balance and depth of each subtree, but Java doesn't allow to return 2 values or pass by pointer. How do we solve this?

    1. One way is to pack them together into a class and return object of the class.
    2. Another way is to use instance variable.
    3. Third way is to reuse the depth information. Since depth of a tree can't be negative, we could use depth = -1 to flag the tree as not balanced. Above code shows this solution.

  • 6
    R

    Use -1 flag to avoid the extra variable.

    public boolean isBalanced(TreeNode root) {
        return getH(root)!=-1;
    }
    public int getH(TreeNode node){
        if(node==null)
            return 0;
        int leftH = getH(node.left);
        if(leftH==-1)
            return -1;
        int rightH = getH(node.right);
        if(rightH==-1)
            return -1;
        if(Math.abs(leftH-rightH)>1)
            return -1;
        return Math.max(rightH, leftH)+1;
    }

  • 0
    O
    	public int maxDepthDiff = -1;
    	
        public boolean isBalanced(TreeNode root) {
        	TreeDepth(root);
            return (maxDepthDiff <= 1);
        }
        /**
         * record the difference for left child depth and right child depth
         * @param root
         * @return
         */
        public int TreeDepth(TreeNode root) {
        	if (null == root) {
        		return 0;
        	}
        	
        	int left = TreeDepth(root.left);
        	int right = TreeDepth(root.right);
        	
        	int depthDiff = Math.abs(left-right);
        	if (maxDepthDiff < depthDiff) {
        		maxDepthDiff = depthDiff;
        	}
        	return (left > right ? left+1 : right+1);
        }

  • 0
    K

    Use the val to store depth, so the recursion is just once

    class Solution {
        public:
            bool isBalanced(TreeNode *root) {
                if(root == NULL)
                    return true;
                bool left = isBalanced(root->left);
                bool right = isBalanced(root->right);
                //judge early so depth does not need be calculated if early unbalanced node found
                if(!left||!right)
                    return false;
                int depthl = (root->left==NULL)?0:root->left->val;
                int depthr = (root->right==NULL)?0:root->right->val;
                int dif = depthl - depthr;
                bool balance = dif<2?(dif>-2?true:false):false;
                if(balance){
                    root->val = max(depthl, depthr) + 1;
                    return true;
                }else
                    return false;
            }
        };

  • 0
    S

    I think it's good to add a check in ifBalanced_helper for result after recursively calling ifBalanced_helper for both left and right children, so you could shortcut the processing.


  • 0
    C
    This post is deleted!

  • 0
    W

    No one use exception to stop recursion? All the supported languages have exception, which will stop the execution if any exception occur.

    # Definition for a  binary tree node
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution:
        def depth(self, root):
            if not root:
                return 0;
            left = self.depth(root.left)
            right = self.depth(root.right)
            diff = left-right
            if diff > 1 or diff < -1:
                raise Exception("not balance")
            return left > right and left + 1 or right + 1
        # @param root, a tree node
        # @return a boolean
        def isBalanced(self, root):
            try:
                self.depth(root)
            except:
                return False
            return True

  • 0
    Z

    Hi, us917! Could you please explain to me why the last line is: return max of left height and right height +? Could we simply return False here? Thanks!!


  • 0
    S
    This post is deleted!

Log in to reply
 

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