110. 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 ofeverynode never differ by more than 1.

题目大意：

判断一颗二叉树是否为平衡二叉树。

思路：

做一个辅助函数来求的树的高度。

通过辅助函数来递归求解。


代码如下：

/***Definitionforabinarytreenode.*structTreeNode{*intval;*TreeNode*left;*TreeNode*right;*TreeNode(intx):val(x),left(NULL),right(NULL){}*};*/classSolution{public:intdepth(TreeNode*root){if(!root)return0;intl=depth(root->left);intr=depth(root->right);return1+((l>r)?l:r);}boolisBalanced(TreeNode*root){if(!root)returntrue;else{intl=depth(root->left);intr=depth(root->right);if(l+1<r||r+1<l){returnfalse;}elsereturn(isBalanced(root->left)&&isBalanced(root->right));}}};


2016-08-08 00:25:26