【LeetCode】110. Balanced Binary Tree

问题描述

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。

问题分析

遍历树，对于每个节点，求出其左右子树的高度，然后判断两者的差是否大于1，大于1，直接返回False；否则，继续遍历左子树和右子树。

代码

class Solution {
public:
    bool isBalanced(TreeNode* root) {
    	if(root==0) return true;
		if(root->left==0&&root->right==0) return true;
		TreeNode* p = root;
		int r = depth(p->right,0);
		int l = depth(p->left,0);
		if(abs(r-l)>1) {
			return false;
		}
		return isBalanced(p->left)&&isBalanced(p->right);   
    }
    
    int depth(TreeNode* p, int level) {
        if(p==0) return level;
        level++;
        int l1 = depth(p->left, level);
        int l2 = depth(p->right, level);
        return l1>l2?l1:l2;
    } 
};