Balanced Binary TreeOct 9 '127722 / 18479
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 ofevery node never differ by more than 1.
看清题目很重要!
这里balance的定义:任意子树的depth,相差都不超过1。
其实,我觉得balance的定义还可以是另外一种:任意两个叶节点(这里叶节点为null节点)的depth相差不超过1。这样的话,方法就变一下。不过大体还是相同的。
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: bool isBalanced(TreeNode *root) { int l; return check(root, l); } bool check(TreeNode* cur, int &len) { if (cur == 0) { len = 0; return true; } int l, r; if (check(cur->left, l) && check(cur->right, r)) { len = max(l, r) + 1; return abs(l - r) <= 1; } return false; } };