Balanced Binary Tree

Easy

Given the root of a binary tree, determine if it is height-balanced. A binary tree is height-balanced if the absolute difference between the heights of the left subtree and the right subtree of any node is no more than 1 for all nodes.

Example 1

Input

[
  3,
  9,
  20,
  null,
  null,
  15,
  7
]

Output

true

Explanation. This binary tree is structured as follows: 3 / \ 9 20 / \ 15 7 It is balanced as the height of the left subtree (1) and the right subtree (2) of the root differ by 1, which satisfies the height-balanced condition.

Example 2

Input

[
  1,
  2,
  2,
  3,
  3,
  null,
  null,
  4,
  4
]

Output

false

Explanation. This binary tree is structured as follows: 1 / \ 2 2 / \ 3 3 / \ 4 4 This tree is not balanced as the height difference between the left subtree (3) and the right subtree (1) of node 2 includes a difference greater than 1.

Example 3

Input

[]

Output

true

Explanation. An empty tree is considered height-balanced.

Follow-up: Can you solve the problem in O(n) time complexity?

Constraints:

The number of nodes in the tree will be in the range [0, 5000]. Each node's value is an integer between -100000 and 100000.

Views: 14

Balanced Binary Tree

Solution

Judge

Balanced Binary Tree

Discussion (0)

Solution

Judge