LeetCode Algorithm 剑指 Offer 55 - II. 平衡二叉树

55 - II. 平衡二叉树

Ideas

这题直接扣平衡二叉树的定义就可以了，需要写一个辅助函数用来计算二叉树的高度，然后计算根节点左右子树的高度差，满足深度相差不超过1，那么它就是一棵平衡二叉树。

Code C++

class Solution { public: int get_height(TreeNode* node) { if (node == NULL) { return 0; } else { return max(get_height(node->left), get_height(node->right)) + 1; } } bool isBalanced(TreeNode* root) { if (root == NULL) { return true; } int left_height = get_height(root->left); int right_height = get_height(root->right); return abs(left_height - right_height) < 2 && isBalanced(root->left) && isBalanced(root->right) ? true : false; } }; 

极限压缩版：

class Solution { public: int get_height(TreeNode* node) { return node == NULL ? 0 : max(get_height(node->left), get_height(node->right)) + 1; } bool isBalanced(TreeNode* root) { return root == NULL ? true : abs(get_height(root->left) - get_height(root->right)) < 2 && isBalanced(root->left) && isBalanced(root->right) ? true : false; } };