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.
思考:求二叉樹高的變形,加上判斷即可。
/*** Definition for binary tree* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
private:bool flag;
public:int DFS(TreeNode *root){if(root){int height1=DFS(root->left);int height2=DFS(root->right);if(abs(height1-height2)>1) flag=false;return max(height1,height2)+1;}else return 0;}bool isBalanced(TreeNode *root) {flag=true;int height=DFS(root);//樹高return flag;}
};