Sum Tree

Given a binary tree root, return whether for every node in the tree other than the leaves, its value is equal to the sum of its left child’s value and its right child’s value.

Constraints

• n ≤ 100,000 where n is the number of nodes in root

https://binarysearch.com/problems/Sum-Tree

Examples

Example 1

Input

• root =

Output

• answer = True

Example 2

Input

• root =

Output

• answer = False

Solution