判断给定的二叉树是否是平衡二叉树
平衡二叉树的性质为: 要么是一棵空树，要么任何一个节点的左右子树高度差的绝对值不超过 1。
一颗树的高度指的是树的根节点到所有节点的距离中的最大值。
最初的想法肯定是先求出每个节点的左右子树的高度,如果差距不超过1再用递归的方式判断其左右子节点是否平衡.而求高度的方法也用递归的方法,所以需要用到多重递归:
/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ class Solution { public: /** * * @param root TreeNode类 * @return bool布尔型 */ bool isBalanced(TreeNode* root) { // write code here if (root) { if (abs(height(root->left) - height(root->right)) <= 1) { return (isBalanced(root->left) && isBalanced(root->right)); } else { return false; } } return true; } int height(TreeNode* root) { int h = 0; if (root) { int l = height(root->left); int r = height(root->right); h = 1 + (l > r ? l : r); } return h; } };本来以为性能会很差,结果还可以:
