You are given the root of a binary tree where each node has a value 0 or 1. Each root-to-leaf path represents a binary number starting with the most significant bit.
0 -> 1 -> 1 -> 0 -> 1, then this could represent 01101 in binary, which is 13.For all leaves in the tree, consider the numbers represented by the path from the root to that leaf. Return the sum of these numbers.
The test cases are generated so that the answer fits in a 32-bits integer.
Example 1:
Input: root = [1,0,1,0,1,0,1] Output: 22 Explanation: (100) + (101) + (110) + (111) = 4 + 5 + 6 + 7 = 22
Example 2:
Input: root = [0] Output: 0
Constraints:
[1, 1000].Node.val is 0 or 1.program main
use, intrinsic :: iso_fortran_env, only : error_unit, DP => REAL64
implicit none
integer, parameter :: n = 8
type :: Node
integer :: val
class(Node), pointer :: left, right
end type
type(Node), target :: root
integer :: i, j
real(kind=DP) :: x
! Examples
call solve([1,0,1,0,1,0,1], x)
write (unit=error_unit, fmt='(A,F0.2)') 'Example 1: ', x
call solve([0], x)
write (unit=error_unit, fmt='(A,F0.2)') 'Example 2: ', x
contains
subroutine solve(root, x)
type(Node), intent(in) :: root
real(kind=DP), intent(out) :: x
x = 0.0_DP
do i = 1, n
if (associated(root%left)) then
call solve(root%left, x)
end if
x = x + real(root%val, kind=DP) * 2.0_DP**(n - i)
if (associated(root%right)) then
call solve(root%right, x)
end if
end do
end subroutine solve
end program maintemp.f95:28:40:
28 | call solve(root%left, x)
| 1
Error: SUBROUTINE ‘solve’ at (1) cannot be called recursively, as it is not RECURSIVE
temp.f95:32:41:
32 | call solve(root%right, x)
| 1
Error: SUBROUTINE ‘solve’ at (1) cannot be called recursively, as it is not RECURSIVE
temp.f95:14:34:
14 | call solve([1,0,1,0,1,0,1], x)
| 1
Error: Type mismatch in argument ‘root’ at (1); passed INTEGER(4) to TYPE(node)
temp.f95:16:22:
16 | call solve([0], x)
| 1
Error: Type mismatch in argument ‘root’ at (1); passed INTEGER(4) to TYPE(node)
temp.f95:26:19:
26 | do i = 1, n
| 1
27 | if (associated(root%left)) then
28 | call solve(root%left, x)
| 2
Error: Index variable ‘i’ redefined at (1) in procedure ‘solve’ called from within DO loop at (2)
temp.f95:26:19:
26 | do i = 1, n
| 1
......
32 | call solve(root%right, x)
| 2
Error: Index variable ‘i’ redefined at (1) in procedure ‘solve’ called from within DO loop at (2)
module BinaryTree
implicit none
type :: Node
integer :: val
type(Node), pointer :: left
type(Node), pointer :: right
end type Node
interface
function sum_path_values(root) result(sum)
type(Node), pointer :: root
integer :: sum
end function sum_path_values
end interface
contains
function sum_path_values_helper(root, current_sum) result(sum)
type(Node), pointer :: root
integer :: current_sum
integer :: sum
if (.not. associated(root)) then
sum = 0
else
current_sum = current_sum * 2 + root%val
sum = sum_path_values_helper(root%left, current_sum) + &
sum_path_values_helper(root%right, current_sum)
end if
sum = sum + current_sum
end function sum_path_values_helper
function sum_path_values(root) result(sum)
type(Node), pointer :: root
integer :: sum
sum = sum_path_values_helper(root, 0)
end function sum_path_values
end module BinaryTree
program main
use BinaryTree
implicit none
type(Node), pointer :: root
integer :: sum
! Example 1
root => Node(val=1, left => Node(val=0, left => Node(val=1, left => Node(val=0, left => Node(val=1, left => Node(val=0, left => Node(val=1, left => null()), right => null())), right => null())), right => null())
sum = sum_path_values(root)
write (*,*) "Example 1:", sum
! Example 2
root => Node(val=0, left => null(), right => null())
sum = sum_path_values(root)
write (*,*) "Example 2:", sum
! Example 3
root => Node(val=1, left => Node(val=0, left => Node(val=1, left => Node(val=0, left => Node(val=1, left => Node(val=0, left => Node(val=1, left => null()), right => null())), right => null())), right => null())
sum = sum_path_values(root)
write (*,*) "Example 3:", sum
end program main
temp.f95:13:23:
13 | type(Node), pointer :: root
| 1
Error: Derived type ‘node’ at (1) is being used before it is defined
temp.f95:37:29:
12 | function sum_path_values(root) result(sum)
| 2
......
37 | function sum_path_values(root) result(sum)
| 1
Error: Procedure ‘sum_path_values’ at (1) is already defined at (2)
temp.f95:38:35:
38 | type(Node), pointer :: root
| 1
Error: Unexpected data declaration statement in CONTAINS section at (1)
temp.f95:39:22:
39 | integer :: sum
| 1
Error: Unexpected data declaration statement in CONTAINS section at (1)
temp.f95:41:45:
41 | sum = sum_path_values_helper(root, 0)
| 1
Error: Unexpected assignment statement in CONTAINS section at (1)
temp.f95:43:7:
43 | end function sum_path_values
| 1
Error: Expecting END MODULE statement at (1)
temp.f95:30:40:
30 | sum_path_values_helper(root%right, current_sum)
| 1
Error: Function ‘sum_path_values_helper’ at (1) cannot be called recursively, as it is not RECURSIVE
temp.f95:48:9:
48 | use BinaryTree
| 1
Fatal Error: Cannot open module file ‘binarytree.mod’ for reading at (1): No such file or directory
compilation terminated.
def uniquePathsIII(grid):
x, y, empty = 0, 0, 1
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == 1:
x, y = i, j
elif grid[i][j] == 0:
empty += 1
return dfs(grid, x, y, empty)
def dfs(grid, x, y, empty):
if x < 0 or x >= len(grid) or y < 0 or y >= len(grid[0]) or grid[x][y] == -1:
return 0
if grid[x][y] == 2:
return 1 if empty == -1 else 0
grid[x][y] = -1
paths = dfs(grid, x + 1, y, empty - 1) + dfs(grid, x - 1, y, empty - 1) + dfs(grid, x, y + 1, empty - 1) + dfs(grid, x, y - 1, empty - 1)
grid[x][y] = 0
return paths
The algorithm uses a depth-first search (DFS) to explore all possible paths from the starting square to the ending square while keeping track of the number of non-obstacle squares it has visited. If a path reaches the ending square and has visited all non-obstacle squares exactly once, it counts as a valid path. The algorithm returns the total number of valid paths it finds. It starts by iterating over the grid to find the starting position and count the number of non-obstacle squares. Then it performs the DFS, backtracking when necessary by marking visited squares with -1 and unvisiting them once they have been explored.
int dfs(vector<vector<int>>& grid, int x, int y, int empty) {
if (x < 0 || x >= grid.size() || y < 0 || y >= grid[0].size() || grid[x][y] == -1) {
return 0;
}
if (grid[x][y] == 2) {
return empty == -1 ? 1 : 0;
}
grid[x][y] = -1;
int paths = dfs(grid, x + 1, y, empty - 1) + dfs(grid, x - 1, y, empty - 1) + dfs(grid, x, y + 1, empty - 1) + dfs(grid, x, y - 1, empty - 1);
grid[x][y] = 0;
return paths;
}
int uniquePathsIII(vector<vector<int>>& grid) {
int x = 0, y = 0, empty = 1;
for (int i = 0; i < grid.size(); ++i) {
for (int j = 0; j < grid[0].size(); ++j) {
if (grid[i][j] == 1) {
x = i, y = j;
} else if (grid[i][j] == 0) {
empty++;
}
}
}
return dfs(grid, x, y, empty);
}
The algorithm uses a depth-first search (DFS) to explore all possible paths from the starting square to the ending square while keeping track of the number of non-obstacle squares it has visited. If a path reaches the ending square and has visited all non-obstacle squares exactly once, it counts as a valid path. The algorithm returns the total number of valid paths it finds. It starts by iterating over the grid to find the starting position and count the number of non-obstacle squares. Then it performs the DFS, backtracking when necessary by marking visited squares with -1 and unvisiting them once they have been explored.