Given a binary tree, determine if it is height-balanced.
Example 1:
Input: root = [3,9,20,null,null,15,7] Output: true
Example 2:
Input: root = [1,2,2,3,3,null,null,4,4] Output: false
Example 3:
Input: root = [] Output: true
Constraints:
[0, 5000].-104 <= Node.val <= 104program main
! Solves the problem: Given a binary tree, determine if it is height-balanced.
implicit none
type :: node_t
integer :: val
type(node_t), pointer :: left => null(), right => null()
end type
type(node_t), target :: root
call solve(root)
contains
function is_height_balanced(root) result(is_balanced)
! Determines if the given binary tree is height-balanced.
implicit none
class(node_t), intent(in) :: root
logical :: is_balanced
integer :: depth
is_balanced = .true.
depth = 0
call check_depth(root, depth, is_balanced)
end function
subroutine check_depth(root, depth, is_balanced)
! Recursive function to check the depth of the given binary tree.
implicit none
class(node_t), intent(in) :: root
integer, intent(inout) :: depth
logical, intent(inout) :: is_balanced
if (associated(root%left)) then
call check_depth(root%left, depth + 1, is_balanced)
end if
if (associated(root%right)) then
call check_depth(root%right, depth + 1, is_balanced)
end if
if (abs(depth - get_depth(root%left)) > 1) then
is_balanced = .false.
end if
end subroutine
function get_depth(root) result(depth)
! Returns the depth of the given binary tree.
implicit none
class(node_t), intent(in) :: root
integer :: depth
if (.not. associated(root)) then
depth = 0
else
depth = max(get_depth(root%left), get_depth(root%right)) + 1
end if
end function
subroutine solve(root)
! Runs the solution on the given binary tree.
implicit none
type(node_t), intent(inout) :: root
write (*, '(L1)') is_height_balanced(root)
end subroutine
end programtemp.f95:53:29:
53 | if (.not. associated(root)) then
| 1
Error: ‘pointer’ argument of ‘associated’ intrinsic at (1) must be a POINTER
temp.f95:56:24:
56 | depth = max(get_depth(root%left), get_depth(root%right)) + 1
| 1
Error: Function ‘get_depth’ at (1) cannot be called recursively, as it is not RECURSIVE
temp.f95:36:63:
36 | call check_depth(root%left, depth + 1, is_balanced)
| 1
Error: SUBROUTINE ‘check_depth’ at (1) cannot be called recursively, as it is not RECURSIVE
temp.f95:36:40:
36 | call check_depth(root%left, depth + 1, is_balanced)
| 1
Error: Non-variable expression in variable definition context (actual argument to INTENT = OUT/INOUT) at (1)
temp.f95:39:64:
39 | call check_depth(root%right, depth + 1, is_balanced)
| 1
Error: SUBROUTINE ‘check_depth’ at (1) cannot be called recursively, as it is not RECURSIVE
temp.f95:39:41:
39 | call check_depth(root%right, depth + 1, is_balanced)
| 1
Error: Non-variable expression in variable definition context (actual argument to INTENT = OUT/INOUT) at (1)
module height_balanced_binary_tree
implicit none
contains
function is_height_balanced(root) result(is_balanced)
type(node), pointer, intent(in) :: root
logical :: is_balanced
is_balanced = is_height_balanced_recursive(root)
end function is_height_balanced
recursive function is_height_balanced_recursive(root) result(is_balanced)
type(node), pointer, intent(in) :: root
logical :: is_balanced
integer :: height_left, height_right
if (.not. associated(root)) then
is_balanced = .true.
return
end if
is_balanced = .false.
height_left = height(root%left)
height_right = height(root%right)
if (abs(height_left - height_right) <= 1) then
is_balanced = is_height_balanced_recursive(root%left) .and. &
is_height_balanced_recursive(root%right)
end if
end function is_height_balanced_recursive
function height(root) result(height)
type(node), pointer, intent(in) :: root
integer :: height
if (.not. associated(root)) then
height = 0
return
end if
height = max(height(root%left), height(root%right)) + 1
end function height
type node
integer :: val
type(node), pointer :: left
type(node), pointer :: right
end type node
end module height_balanced_binary_tree
program test
use height_balanced_binary_tree
implicit none
type(node), pointer :: root
! Example 1
root = create_node(3)
root%left = create_node(9)
root%right = create_node(20)
root%left%left = create_node(15)
root%left%right = create_node(7)
if (is_height_balanced(root)) then
write (*,*) "Example 1: Height-balanced"
else
write (*,*) "Example 1: Not height-balanced"
end if
! Example 2
root = create_node(1)
root%left = create_node(2)
root%right = create_node(2)
root%left%left = create_node(3)
root%left%right = create_node(3)
root%right%left = create_node(4)
root%right%right = create_node(4)
if (is_height_balanced(root)) then
write (*,*) "Example 2: Height-balanced"
else
write (*,*) "Example 2: Not height-balanced"
end if
! Example 3
root = null()
if (is_height_balanced(root)) then
write (*,*) "Example 3: Height-balanced"
else
write (*,*) "Example 3: Not height-balanced"
end if
contains
function create_node(val) result(node)
integer, intent(in) :: val
type(node) :: node
allocate(node)
node%val = val
node%left = null()
node%right = null()
end function create_node
end program test
temp.f95:9:15:
9 | type(node), pointer, intent(in) :: root
| 1
Error: Derived type ‘node’ at (1) is being used before it is defined
temp.f95:18:15:
18 | type(node), pointer, intent(in) :: root
| 1
Error: Derived type ‘node’ at (1) is being used before it is defined
temp.f95:30:31:
30 | height_left = height(root%left)
| 1
Error: Symbol ‘root’ at (1) has no IMPLICIT type
temp.f95:31:32:
31 | height_right = height(root%right)
| 1
Error: Symbol ‘root’ at (1) has no IMPLICIT type
temp.f95:34:57:
34 | is_balanced = is_height_balanced_recursive(root%left) .and. &
| 1
Error: Symbol ‘root’ at (1) has no IMPLICIT type
temp.f95:40:36:
40 | function height(root) result(height)
| 1
Error: RESULT variable at (1) must be different than function name
temp.f95:42:15:
42 | type(node), pointer, intent(in) :: root
| 1
Error: Derived type ‘node’ at (1) is being used before it is defined
temp.f95:43:21:
43 | integer :: height
| 1
Error: Symbol ‘height’ at (1) has already been host associated
temp.f95:45:36:
45 | if (.not. associated(root)) then
| 1
Error: Unexpected block IF statement in CONTAINS section at (1)
temp.f95:46:15:
46 | height = 0
| 1
Error: Symbol ‘height’ at (1) has already been host associated
temp.f95:47:14:
47 | return
| 1
Error: Unexpected RETURN statement in CONTAINS section at (1)
temp.f95:48:7:
48 | end if
| 1
Error: Expecting END MODULE statement at (1)
temp.f95:50:11:
50 | height = max(height(root%left), height(root%right)) + 1
| 1
Error: Symbol ‘height’ at (1) has already been host associated
temp.f95:52:3:
52 | end function height
| 1
Error: Expecting END MODULE statement at (1)
temp.f95:54:9:
54 | type node
| 1
Error: Unexpected derived type declaration statement in CONTAINS section at (1)
temp.f95:55:18:
55 | integer :: val
| 1
Error: Unexpected data declaration statement in CONTAINS section at (1)
temp.f95:56:15:
56 | type(node), pointer :: left
| 1
Error: Derived type ‘node’ at (1) is being used before it is defined
temp.f95:57:15:
57 | type(node), pointer :: right
| 1
Error: Derived type ‘node’ at (1) is being used before it is defined
temp.f95:58:3:
58 | end type node
| 1
Error: Expecting END MODULE statement at (1)
temp.f95:7:32:
7 | function is_height_balanced(root) result(is_balanced)
| 1
Error: Symbol ‘root’ at (1) has no IMPLICIT type
temp.f95:16:52:
16 | recursive function is_height_balanced_recursive(root) result(is_balanced)
| 1
Error: Symbol ‘root’ at (1) has no IMPLICIT type
temp.f95:64:5:
64 | use height_balanced_binary_tree
| 1
Fatal Error: Cannot open module file ‘height_balanced_binary_tree.mod’ for reading at (1): No such file or directory
compilation terminated.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def getHeight(node):
if not node:
return 0
left_height = getHeight(node.left)
right_height = getHeight(node.right)
if left_height == -1 or right_height == -1 or abs(left_height - right_height) > 1:
return -1
return 1 + max(left_height, right_height)
def isBalanced(root):
return getHeight(root) != -1
The algorithm is based on the depth-first search. In this algorithm, we define a helper function named `getHeight` which will return the height of the given subtree if it is balanced, otherwise, it will return -1.
The getHeight function works as follows:
1. If the current node is null, return 0 (base case).
2. Call the function recursively for the left subtree (leftHeight) and the right subtree (rightHeight).
3. If either of the subtrees is not balanced or the height difference is greater than 1, return -1.
4. Otherwise, return the maximum height of the left and right subtrees incremented by 1.
The main function isBalanced just calls the getHeight function and checks whether its result is -1 or not. If it is not -1, the binary tree is height-balanced, otherwise, it is not balanced.
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
};
int getHeight(TreeNode* node) {
if (!node) return 0;
int leftHeight = getHeight(node->left);
int rightHeight = getHeight(node->right);
if (leftHeight == -1 || rightHeight == -1 || abs(leftHeight - rightHeight) > 1)
return -1;
return 1 + max(leftHeight, rightHeight);
}
bool isBalanced(TreeNode* root) {
return getHeight(root) != -1;
}
The algorithm is based on the depth-first search. In this algorithm, we define a helper function named `getHeight` which will return the height of the given subtree if it is balanced, otherwise, it will return -1.
The getHeight function works as follows:
1. If the current node is null, return 0 (base case).
2. Call the function recursively for the left subtree (leftHeight) and the right subtree (rightHeight).
3. If either of the subtrees is not balanced or the height difference is greater than 1, return -1.
4. Otherwise, return the maximum height of the left and right subtrees incremented by 1.
The main function isBalanced just calls the getHeight function and checks whether its result is -1 or not. If it is not -1, the binary tree is height-balanced, otherwise, it is not balanced.