My solution, check balance while getting height of sub-tree


  • -2
    S
    class Solution {
    public:
    bool isBalanced(TreeNode *root) {
    	if (postOrderHeight(root) == -1)
    		return false;
    	else return true;
    }
    
    int postOrderHeight(TreeNode *root){
    	if (!root)
    		return 0;
    	if (!root->left && !root->right)
    		return 1;
    
    	int leftH, rightH;
    
    	leftH = postOrderHeight(root->left);
    	if (leftH == -1)
    		return -1;
    
    	rightH = postOrderHeight(root->right);
    	if (rightH == -1)
    		return -1;
    
    	if (abs(leftH - rightH) > 1)
    		return -1;
    	else return max(leftH, rightH) + 1;
     }
    };

Log in to reply
 

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