LeetCode110. 平衡二叉树
平衡二叉树定义：|左子树高度-右子树高度| <= 1
踩坑点：
不能通过根节点的左右子树高度来直接判断是否为平衡二叉树，e.g:假如根节点左子树为左斜树，右子树为右斜树，且两棵子树个数相同，此时根节点左右子树高度相同，但不是平衡二叉树。
因此还是需要一层层地往下判断
class Solution {
public:int max(int a, int b){return a > b ? a : b;}int getHeight(TreeNode* root){if (root == nullptr) return 0;int leftHeight = getHeight(root->left);int rightHeight = getHeight(root->right);return max(leftHeight, rightHeight) + 1;}bool isBalanced(TreeNode* root) { bool res;if (root == nullptr) return true;int leftHeight = getHeight(root->left);int rightHeight = getHeight(root->right);if (abs((leftHeight - rightHeight)) <= 1){if(!isBalanced(root->left)) return false;if(!isBalanced(root->right)) return false;return true;}elsereturn false;}
};