Accepted C++ solution, 19ms


  • -1
    J

    The idea is similar to other solutions. Use depth first, post order traversal and short cut to return fast.

    Another note is to replace abs, max with simple code to improve performance.

    class Solution {
    public:
    	int max(int a, int b)
    	{
    		if(a>=b)
    			return a;
    		return b;
    	}
    
        bool isBalanced(TreeNode *root) {
    		bool ret = true;
    		int ldep, rdep, diff;
    
            if (root == NULL)
    			return true;
    		
    		if (root->left)
    		{	
    			if (!isBalanced( root->left ))
    				return false;
    			ldep = root->left->val + 1;
    		}
    		else
    			ldep=0;
    
    		if ( root->right)
    		{
    			if (!isBalanced( root->right ))
    				return false;
    			rdep = root->right->val + 1;
    		}
    		else
    			rdep = 0;
    				
    
    		diff = ldep - rdep;
    
    		if ( diff >1 || diff <-1 )
    			return false;
    		else
    			root->val = max(ldep, rdep);
    
    		return true;
        }
        
    };

  • 0
    A

    This is wrong... you are changing val root->val = max(ldep, rdep);


  • 0
    J

    In the question, I don't see any requirement to keep the val unchanged.


  • 0
    O

    @jin15

    It is common sense to keep the val unchanged! Don't need special specification.
    If you just use the val to store the layer information, what is the tree used for?


Log in to reply
 

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