Balanced Binary Tree

Binary TreeDepth-First SearchTree

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: 3