Balanced Binary Tree

Nov 13, 2017


今天的题目是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.


bool isBalanced(TreeNode* root) {
    int h = 0;
    return isBalanced(root,h);
bool isBalanced(TreeNode *root,int &height) {
    if (root == nullptr) { height = 0; return true; }
    int left,right;
    if (!isBalanced(root->left,left) || !isBalanced(root->right,right))
        return false;

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

    height = max(left,right) + 1;
    return true;


class Solution:
    def isBalanced(self,root):
        :type root: TreeNode
        :rtype: bool
        res,height = self.isBalancedRec(root)
        return res

    def isBalancedRec(self, root):
        :type root: TreeNode
        :rtype: bool,int
        if root is None:
            return True,0

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

        if leftRes == False or rightRes == False:
            return False,max(leftH,rightH)
            return abs(leftH-rightH) <= 1,max(leftH,rightH)+1

Symmetric Tree

Climbing Stairs

comments powered by Disqus