In a binary tree, a lonely node is a node that is the only child of its parent node. The root of the tree is not lonely because it does not have a parent node.
Given the root of a binary tree, return an array containing the values of all lonely nodes in the tree. Return the list in any order.
Example 1:
Input: root = [1,2,3,null,4] Output: [4] Explanation: Light blue node is the only lonely node. Node 1 is the root and is not lonely. Nodes 2 and 3 have the same parent and are not lonely.
Example 2:
Input: root = [7,1,4,6,null,5,3,null,null,null,null,null,2] Output: [6,2] Explanation: Light blue nodes are lonely nodes. Please remember that order doesn't matter, [2,6] is also an acceptable answer.
Example 3:
Input: root = [11,99,88,77,null,null,66,55,null,null,44,33,null,null,22] Output: [77,55,33,66,44,22] Explanation: Nodes 99 and 88 share the same parent. Node 11 is the root. All other nodes are lonely.
Constraints:
tree is in the range [1, 1000].1 <= Node.val <= 106program lonely_nodes
use, intrinsic :: iso_fortran_env, only : error_unit, DP => REAL64
implicit none
integer, parameter :: unit_out = 6
type :: node
real(kind=DP) :: val
class(node), pointer :: left => null(), right => null()
end type
type(node), pointer :: root
integer :: i
character(len=*), parameter :: fmt = '(*(g0,:," ",:," ",:))'
call get_examples(root)
do i = 1, size(root%left)
if (associated(root%left(i)%left)) then
write (unit=unit_out, fmt=fmt) root%val, &
root%left(i)%val, root%left(i)%left%val
else
write (unit=unit_out, fmt=fmt) root%val, &
root%left(i)%val, "None"
end if
end do
deallocate (root)
contains
subroutine get_examples(root)
implicit none
type(node), pointer :: root
allocate (root)
root%val = 1.0_DP
allocate (root%left(2))
root%left(1)%val = 2.0_DP
allocate (root%left(2)%left)
root%left(2)%left%val = 3.0_DP
allocate (root%right)
root%right%val = 4.0_DP
end subroutine get_examples
end program lonely_nodestemp.f95:15:33:
15 | if (associated(root%left(i)%left)) then
| 1
Error: Syntax error in argument list at (1)
temp.f95:17:26:
17 | root%left(i)%val, root%left(i)%left%val
| 1
Error: Syntax error in WRITE statement at (1)
temp.f95:18:12:
18 | else
| 1
Error: Unexpected ELSE statement at (1)
temp.f95:20:26:
20 | root%left(i)%val, "None"
| 1
Error: Syntax error in WRITE statement at (1)
temp.f95:21:11:
21 | end if
| 1
Error: Expecting END DO statement at (1)
temp.f95:32:28:
32 | allocate (root%left(2))
| 1
Error: Shape specification for allocatable scalar at (1)
temp.f95:34:28:
34 | allocate (root%left(2)%left)
| 1
Error: Shape specification for allocatable scalar at (1)
temp.f95:14:19:
14 | do i = 1, size(root%left)
| 1
Error: ‘array’ argument of ‘size’ intrinsic at (1) must be an array
module lonely_nodes
implicit none
contains
function get_lonely_nodes(root) result(lonely_nodes)
! Return an array containing the values of all lonely nodes in the tree
type(node), pointer :: root
integer, allocatable :: lonely_nodes(:)
! Initialize the array to store the lonely nodes
allocate(lonely_nodes(0))
! Traverse the tree and mark the lonely nodes
call traverse(root, lonely_nodes)
end function get_lonely_nodes
subroutine traverse(node, lonely_nodes)
! Traverse the tree and mark the lonely nodes
type(node), pointer :: node
integer, allocatable :: lonely_nodes(:)
! Base case: If the node is null, return
if (.not. associated(node)) return
! If the node is a lonely node, add its value to the array
if (node%is_lonely()) then
lonely_nodes = lonely_nodes + [node%val]
end if
! Recursively traverse the left and right subtrees
call traverse(node%left, lonely_nodes)
call traverse(node%right, lonely_nodes)
end subroutine traverse
end module lonely_nodes
program test
use lonely_nodes
implicit none
! Test case 1:
type(node), pointer :: root
allocate(root)
root%val = 1
root%left => null()
root%right => null()
write(*,*) get_lonely_nodes(root)
! Test case 2:
deallocate(root)
allocate(root)
root%val = 7
root%left => null()
root%right => null()
root%left => new_node(1)
root%right => new_node(2)
write(*,*) get_lonely_nodes(root)
! Test case 3:
deallocate(root)
allocate(root)
root%val = 11
root%left => null()
root%right => null()
root%left => new_node(99)
root%right => new_node(88)
root%left%left => new_node(77)
root%left%right => new_node(66)
root%right%left => new_node(55)
root%right%right => new_node(44)
root%left%left%left => new_node(33)
root%left%left%right => new_node(22)
write(*,*) get_lonely_nodes(root)
contains
type(node), pointer function new_node(val)
! Create a new node with the given value
integer, intent(in) :: val
type(node), pointer :: new_node
allocate(new_node)
new_node%val = val
new_node%left => null()
new_node%right => null()
end function new_node
end program test
temp.f95:11:11:
11 | type(node), pointer :: root
| 1
Error: Derived type ‘node’ at (1) is being used before it is defined
temp.f95:26:11:
26 | type(node), pointer :: node
| 1
Error: Derived type ‘node’ at (1) is being used before it is defined
temp.f95:33:10:
33 | if (node%is_lonely()) then
| 1
Error: Symbol ‘node’ at (1) has no IMPLICIT type
temp.f95:34:37:
34 | lonely_nodes = lonely_nodes + [node%val]
| 1
Error: Symbol ‘node’ at (1) has no IMPLICIT type
temp.f95:35:3:
35 | end if
| 1
Error: Expecting END SUBROUTINE statement at (1)
temp.f95:38:20:
38 | call traverse(node%left, lonely_nodes)
| 1
Error: Symbol ‘node’ at (1) has no IMPLICIT type
temp.f95:39:20:
39 | call traverse(node%right, lonely_nodes)
| 1
Error: Symbol ‘node’ at (1) has no IMPLICIT type
temp.f95:7:30:
7 | function get_lonely_nodes(root) result(lonely_nodes)
| 1
Error: Symbol ‘root’ at (1) has no IMPLICIT type
temp.f95:22:24:
22 | subroutine traverse(node, lonely_nodes)
| 1
Error: Symbol ‘node’ at (1) has no IMPLICIT type
temp.f95:47:5:
47 | use lonely_nodes
| 1
Fatal Error: Cannot open module file ‘lonely_nodes.mod’ for reading at (1): No such file or directory
compilation terminated.
def min_steps(s, t):
count_s = [0] * 26
count_t = [0] * 26
steps = 0
for c in s:
count_s[ord(c) - ord('a')] += 1
for c in t:
count_t[ord(c) - ord('a')] += 1
for i in range(26):
steps += abs(count_s[i] - count_t[i])
return steps // 2
countS and countT of size 26 (to represent the English alphabet) and fill it with zeros.s and increment the count of each character in countS.t and increment the count of each character in countT.countS and countT, and add the differences to a variable steps.steps since the question asks for the minimum number of steps to make t an anagram of s. All differences in characters count are double-accounted when calculating the absolute difference (e.g., one less of a character in t also counts as one more of the same character in s).#include <string>
#include <vector>
using namespace std;
int minSteps(string s, string t) {
vector<int> countS(26, 0);
vector<int> countT(26, 0);
int steps = 0;
for (char c : s) countS[c - 'a']++;
for (char c : t) countT[c - 'a']++;
for (int i = 0; i < 26; i++) {
steps += abs(countS[i] - countT[i]);
}
return steps / 2;
}
countS and countT of size 26 (to represent the English alphabet) and fill it with zeros.s and increment the count of each character in countS.t and increment the count of each character in countT.countS and countT, and add the differences to a variable steps.steps since the question asks for the minimum number of steps to make t an anagram of s. All differences in characters count are double-accounted when calculating the absolute difference (e.g., one less of a character in t also counts as one more of the same character in s).