> For the complete documentation index, see [llms.txt](https://kongchengzhuge.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://kongchengzhuge.gitbook.io/leetcode/110.-balanced-binary-tree.md).

# 110. Balanced Binary Tree

## problem description

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 left and right subtrees of every node differ in height by no 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.

## algorithm thought

二叉树问题，判断是否不是平衡二叉树。平衡二叉树定义是左右子树高度差要小于等于1.于是这题变成了类似求二叉树高度的问题。之前也做过二叉树高度问题，直接递归解决。这里只需要在求出高度之后加入一个判断。如果不是平衡的如何处理。求高度的函数，返回值必须是int而不是bool，这就是我们面临的问题。一种解决方案是把求高度的照搬过来，加一个全局变量，如果不平衡，全局变量为false。我们这里用另一种方法，如果不平衡，返回INT\_MAX.由于题目中不存在这么大的二叉树，所以INT\_MAX和任何子树组合都是不平衡的，最后INT\_MAX会传递到调用函数，最后判断是否为INT\_MAX来觉得返回true还是false

## code

```cpp
/**
 * 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 {
public:
    bool isBalanced(TreeNode* root) {
        if(isBalan(root)==INT_MAX)
            return false;
        return true;
    }
    int isBalan(TreeNode* root){
        if(root==NULL)
            return 0;
        int lefth=isBalan(root->left);
        int righth=isBalan(root->right);        
        if(lefth==INT_MAX||righth==INT_MAX||abs(lefth-righth)>1)
            return INT_MAX;        
        return max(lefth,righth)+1;
    }
};
```

## algorithm analysis

时间复杂度O(n),就是遍历问题，遍历所有节点之后会得到结果


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://kongchengzhuge.gitbook.io/leetcode/110.-balanced-binary-tree.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.