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.
题意:给一棵二叉树,判断它是否是平衡二叉树(即每个节点的左右子树深度之差不大于1).
题解:dfs的简单应用。有一个技巧是:用返回-1来表示不行。
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: int dfs(TreeNode *r){ if(r==NULL){ return 0; } int ll=dfs(r->left); int rr=dfs(r->right); if(rr==-1||ll==-1||abs(ll-rr)>1){ return -1; } else{ return max(ll,rr)+1; } } bool isBalanced(TreeNode* root) { if(dfs(root)==-1){ return false; } else{ return true; } } };