【Leetcode】110. Balanced Binary Tree（平衡二叉树）

小灰灰 2022-02-17 14:35 179阅读 0赞

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.

**Example 1:**

Given the following tree `[3,9,20,null,null,15,7]`:

3
       / \
      9  20
        /  \
       15   7

Return true.  
  
**Example 2:**

Given the following tree `[1,2,2,3,3,null,null,4,4]`:

1
          / \
         2   2
        / \
       3   3
      / \
     4   4

Return false.

题目大意：

判断给出的二叉树是否为平衡二叉树。

平衡二叉树的定义：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，**并且左右两个子树都是一棵平衡二叉树**。

解题思路：

递归求解，判断左右两边的最大深度差值是否大于1。

/**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    private:
        int helper(TreeNode *root){
            
            if(root==NULL){
                return 0;
            }
            
            int l = helper(root->left);
            int r = helper(root->right);
            
            if (l == -1 or r==-1 or abs(l-r)>1){
                return -1;
            }
            
            return max(l,r)+1;
        }
    public:
        bool isBalanced(TreeNode* root) {
            
            return helper(root)!=-1;
            
        }
    };