# Balanced Binary Tree

<https://leetcode.com/problems/balanced-binary-tree/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 depth of the two subtrees of every node never differ by more than 1.

## Thoughts

看到二叉树先想分治。这道题和上道题的区别在于不只是记录深度，还要进行比较。\
直接的想法是用两次分治，外层判断isBalanced, isBalanced内部再用分治算depth。\
但这么做会重复计算树的深度，时间复杂度O(n^2).\
此时我们可以对depth()进行特殊处理，让它在算深度时判断是否balanced, 如果不balance直接返回-1。\
因为我们的目标不是计算深度，而是只要有imbalanced就返回即可。

## Code

```
class Solution {

    private int depth(TreeNode node) {
        if (node == null) {
            return 0;
        }

        int left = depth(node.left);
        int right = depth(node.right);

        if (left == -1 || right == -1 || Math.abs(left - right) > 1) {
            return -1;
        }

        return Math.max(left, right) + 1;
    }

    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        if (depth(root) == -1) {
            return false;
        } else {
            return true;
        }
    }

}
```

## Analysis

一次分治遍历: O(n)

## Ver.2

用stack帮助遍历, 用map记录每个遇到过的节点它的子树最大深度.

```
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        Stack<TreeNode> stack = new Stack<>();
        Map<TreeNode, Integer> map = new HashMap<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if ((node.left == null || node.left != null && map.containsKey(node.left)) 
               && (node.right == null || node.right != null && map.containsKey(node.right))) {
                int left = node.left == null ? 0 : map.get(node.left);
                int right = node.right == null ? 0 : map.get(node.right);
                if (Math.abs(left - right) > 1) {
                    return false;
                }
                map.put(node, Math.max(left, right) + 1);
            } else {
                if (node.left != null && !map.containsKey(node.left)) {
                    stack.push(node);
                    stack.push(node.left);
                } else {
                    stack.push(node);
                    stack.push(node.right);
                }
            }
        }
        return true;
    }
}
```


---

# Agent Instructions: 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://hao-fu-1.gitbook.io/oj/binary_tree_and_divide_conquer/divide-and-concquer/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.