LintCode (93) 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.

分治老给我个印象，就是只是返回个bool或者数，其实不是。。。还可以带一个reference parameter,或者放到member里去存着。。。

这个题目乍一看，比较一下左面和右面的max depth就好了，但是又不能一个一个比较,因为只要有一个节点不是，我们就可以全部返回了。 所以这里就用返回+参数的办法。。。

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 33 34 35 36 37 38 39 40 41

/** * 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 int h; return isBalancedHelper(root, h); } bool isBalancedHelper(TreeNode* root, int& h){ if (!root){ h=0; return true; } int left,right; bool isLeft=isBalancedHelper(root->left, left); if (!isLeft) return false; bool isRight=isBalancedHelper(root->right, right); if (!isRight) return false; h=max(left,right)+1; return abs(left-right)<=1; } };