Balanced Binary Tree

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Have you met this question in a real interview? 

Yes

Example

Given binary tree A={3,9,20,#,#,15,7}, B={3,#,20,15,7}

A)  3            B)    3 
   / \                  \
  9  20                 20
    /  \                / \
   15   7              15  7

The binary tree A is a height-balanced binary tree, but B is not.

postorder the BST, get the max depth of left and right side and return the value;
if not height-balanced, return -1

Time: O(n)
Space: O(logn)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

/** * Definition of TreeNode: * class TreeNode { * public: * int val; * TreeNode *left, *right; * TreeNode(int val) { * this->val = val; * this->left = this->right = NULL; * } * } */ class Solution { public: /** * @param root: The root of binary tree. * @return: True if this Binary tree is Balanced, or false. */ bool isBalanced(TreeNode *root) { // write your code here if(helper(root) == -1) return false; return true; } int helper(TreeNode *node){ if(node == NULL) return 0; int left = helper(node->left); int right = helper(node->right); if(left == -1 || right == -1) return -1; if(abs(left - right) > 1) return -1; return max(left, right) + 1; } };