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;
    }
};