Balanced Binary Tree
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.
Solution:
Recursion. Check the left and right subtrees; store the height during recursion in order to compare the subtrees.
However, the following code calls the depth() so many times, and it is inefficient.
The following version is better: every time we found that the subtree is not balanced, we could return -1 and break the recursions.
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.
Solution:
Recursion. Check the left and right subtrees; store the height during recursion in order to compare the subtrees.
However, the following code calls the depth() so many times, and it is inefficient.
The following version is better: every time we found that the subtree is not balanced, we could return -1 and break the recursions.
Comments
Post a Comment