Can we have a better solution


  • 0
    S

    Thanks for your post. However it would be better to share solution with correct code format and elaborated thoughts. Please read the Discuss FAQ for more info. Take a look at good sharing example


  • 0
    T

    I agree with shengwei.li.58, the code above didn't use shortcut in most efficient way in fact.


  • 0
    W
    This post is deleted!

  • 0
    K

    here is my solution:

    class Solution {
    public:
        bool isBalanced(TreeNode *root) {
            return do(root).first;
        }
        pair<bool,int> do(TreeNode *root){
            if(!root) return make_pair(true,0);
            pair<bool,int> a = do(root->left);
            pair<bool,int> b = do(root->right);
            if(!a.first||!b.first) return make_pair(false,0);
            if(abs(a.second-b.second)>1)
                return make_pair(false,0);
            return make_pair(true,(a.second>b.second?a.second:b.second)+1);
        }
    };

  • 0
    S
    bool isBalanced(node root) {
      if(!root) return true;
      bool left = isBalanced(root->left), right = isBalanced(root->right);
      int left_dep = root->left ? root->left->val : 0,
          right_dep = root->right ? root->right->val : 0;
      root->val = max(left_dep, right_dep) + 1;
      return left && right && abs(left_dep-right_dep)<2;
    }
    

    since the node value is not used in this question, i use it to store the depth.


  • 0
    R

    Dynamic Programming & Short-Circuit

    No need to calculate the height of same nodes repeatedly.

    private static HashMap<TreeNode, Integer> treeHeightMap = new HashMap<>(); //for "memorizing" computed heights
    
    public boolean isBalanced(TreeNode root) {
        if(null == root) return true;
        // my left son is balanced && my right son is balanced && I'm balanced
    	return isBalanced(root.left) && isBalanced(root.right) && ((Math.abs(computeHeight(root.left) - computeHeight(root.right))) < 2);
    }
    
    private static int computeHeight(TreeNode root){
    	if(null == root) return -1;
    	Integer height;
    	if (null == (height = treeHeightMap.get(root))){
    		height = Math.max(computeHeight(root.left), computeHeight(root.right)) + 1;
    		treeHeightMap.put(root, height);
    	}
    	return height;
    }

  • 2
    Z

    //The time complexity is O(N),but yous are O(N logN).

      public boolean isBalanced2(TreeNode root) {
    	if(checkHeight(root) == -1)
    		return false;
    	else 
    		return true;
    }
    private int checkHeight(TreeNode root){
    	if(root == null)
    		return 0;
    	
    	int leftHeight = checkHeight(root.left);
    	if(leftHeight == -1)
    		return -1;
    
    	int rightHeight = checkHeight(root.right);
    	if(rightHeight == -1)
    		return -1;
    	
    	int heightDiff = leftHeight - rightHeight;
    	if(Math.abs(heightDiff) > 1)
    		return -1;
    	else
    		return Math.max(leftHeight,rightHeight)+1;
    }
    

  • 0
    Z

    The time complexith is O(N),but yous are O(N longN).

    public boolean isBalanced2(TreeNode root) {
    	if(checkHeight(root) == -1)
    		return false;
    	else 
    		return true;
    }
    
    private int checkHeight(TreeNode root){
    	if(root == null)
    		return 0;
    	
    	int leftHeight = checkHeight(root.left);
    	if(leftHeight == -1)
    		return -1;//not balance
    
    	int rightHeight = checkHeight(root.right);
    	if(rightHeight == -1)
    		return -1;//not balance
    	
    	int heightDiff = leftHeight - rightHeight;
    	if(Math.abs(heightDiff) > 1)
    		return -1;//not balance
    	else
    		return Math.max(leftHeight,rightHeight)+1;//balance,return the true height
    }

  • 0
    M
    This post is deleted!

  • 0
    M
    class Solution:
        # @param root, a tree node
        # @return a boolean
        def isBalanced(self, root):
            h, b = self.getHB(root)
            return b
        
        def getHB(self, root):
            if not root:
                return 0, True
            h1, b1 = self.getHB(root.left)
            h2, b2 = self.getHB(root.right)
            h = max(h1, h2) + 1
            b = b1 and b2 and abs(h1-h2) <= 1
            return h, b
    

    one recursion


  • 0
    C

    I tried to nest getHeight() within isBalanced(), but got an error? Can you do that?


  • 0
    N

    Will it lead to stack overflow? I have the same kind of code and it blows.


  • 0

    if(root == null || isBalanced == false)

    This will end unnecessary traversal.


Log in to reply
 

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