Code & Func

第47天。

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
bool isBalanced(TreeNode* root) {
2
    int h = 0;
3
    return isBalanced(root,h);
4
}
5
bool isBalanced(TreeNode *root,int &height) {
6
    if (root == nullptr) { height = 0; return true; }
7
    int left,right;
8
    if (!isBalanced(root->left,left) || !isBalanced(root->right,right))
9
        return false;
10

11
    if (abs(left - right) > 1) return false;
12

13
    height = max(left,right) + 1;
14
    return true;
15
}

准备把主力语言往python和c上靠，所以以后都会写多一个python的解法。

1
class Solution:
2
    def isBalanced(self,root):
3
        """
4
        :type root: TreeNode
5
        :rtype: bool
6
        """
7
        res,height = self.isBalancedRec(root)
8
        return res
9

10
    def isBalancedRec(self, root):
11
        """
12
        :type root: TreeNode
13
        :rtype: bool,int
14
        """
15
        if root is None:
9 collapsed lines
16
            return True,0
17

18
        leftRes,leftH = self.isBalancedRec(root.left)
19
        rightRes,rightH = self.isBalancedRec(root.right)
20

21
        if leftRes == False or rightRes == False:
22
            return False,max(leftH,rightH)
23
        else:
24
            return abs(leftH-rightH) <= 1,max(leftH,rightH)+1