【关关的刷题日记64】Leetcode 110 Balanced Binary Tree- 专知

【关关的刷题日记64】Leetcode 110 Balanced Binary Tree

点击上方“专知”，关注获取专业AI知识”

关关的刷题日记64 – 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、该树的左右子树都是平衡树 2、该树的左右子树的深度差不超过1。判断该树的左右子树是否是平衡树的过程和判断这棵树是否是平衡树的过程一样，采用递归的思路。

class Solution {public:
    int depth(TreeNode* root)
    {
        if (root==nullptr)
            return 0;
        int count=0,left=1,right=1;
        left+=depth(root->left);
        right+=depth(root->right);
        return max(left, right);
    }

    bool isBalanced(TreeNode* root) {
        if(!root)
            return true;
        int l=depth(root->left), r=depth(root->right);
        return (l==r || l==r+1 || l==r-1) && isBalanced(root->left) && isBalanced(root->right); 
    }};