Given the root of a binary tree, construct a string consisting of parenthesis and integers from a binary tree with the preorder traversal way, and return it.
Omit all the empty parenthesis pairs that do not affect the one-to-one mapping relationship between the string and the original binary tree.
Example 1:
Input: root = [1,2,3,4] Output: "1(2(4))(3) " Explanation: Originally, it needs to be "1(2(4)())(3()()) ", but you need to omit all the unnecessary empty parenthesis pairs. And it will be "1(2(4))(3) "
Example 2:
Input: root = [1,2,3,null,4] Output: "1(2()(4))(3) " Explanation: Almost the same as the first example, except we cannot omit the first parenthesis pair to break the one-to-one mapping relationship between the input and the output.
Constraints:
[1, 104].-1000 <= Node.val <= 1000program main
! Solve the problem described in the task
implicit none
type :: node_t
integer :: val
type(node_t), pointer :: left => null(), right => null()
end type
type(node_t), target :: root
character(len=:), allocatable :: str
call solve(root, str)
write (unit=*, fmt='(A)') trim(str)
contains
subroutine solve(root, str)
! Solve the problem
implicit none
class(node_t), intent(inout) :: root
character(len=:), allocatable, intent(out) :: str
integer :: i, j, k, n
character(len=:), allocatable :: tmp
if (.not. associated(root%left)) then
! If there are no children, just print the value
allocate (character(len=len(trim(str))) :: tmp)
write (tmp, fmt='(I0)') root%val
str = trim(adjustl(tmp)) // ' ' // str
deallocate (tmp)
else
! Otherwise, recurse on both children
call solve(root%left, str)
call solve(root%right, str)
end if
! Omit any empty parenthesis pairs that don't affect the one-to-one
! mapping relationship between the string and the original binary tree
n = len_trim(str)
do i = 1, n - 1
if (str(i:i+1) == '()') then
j = i + 2
do while (j <= n .and. str(j:j) /= ')')
j = j + 1
end do
if (j > n) exit
if (str(j:j) == ')') then
k = j - 1
do while (k >= 1 .and. str(k:k) /= '(')
k = k - 1
end do
if (k < 1) exit
if (str(k:k+1) == '(())') then
str = str(:i-1) // str(j+1:)
end if
end if
end if
end do
end subroutine
end programtemp.f95:34:38:
34 | call solve(root%left, str)
| 1
Error: SUBROUTINE ‘solve’ at (1) cannot be called recursively, as it is not RECURSIVE
temp.f95:35:39:
35 | call solve(root%right, str)
| 1
Error: SUBROUTINE ‘solve’ at (1) cannot be called recursively, as it is not RECURSIVE
module binary_tree_preorder_traversal
implicit none
private
public :: binary_tree_preorder_traversal
type :: binary_tree_node
integer :: val
type(binary_tree_node), pointer :: left
type(binary_tree_node), pointer :: right
end type binary_tree_node
contains
recursive function binary_tree_preorder_traversal(root) result(output)
type(binary_tree_node), pointer, intent(in) :: root
character(len=:), allocatable :: output
if (associated(root)) then
output = trim(adjustl(str(root%val))) // &
binary_tree_preorder_traversal(root%left) // &
binary_tree_preorder_traversal(root%right)
else
output = ""
end if
end function binary_tree_preorder_traversal
end module binary_tree_preorder_traversal
program test_binary_tree_preorder_traversal
use binary_tree_preorder_traversal
implicit none
type(binary_tree_node), pointer :: root
character(len=:), allocatable :: output
! Example 1
root => binary_tree_node(1, &
binary_tree_node(2, &
binary_tree_node(4), &
null()), &
binary_tree_node(3))
output = binary_tree_preorder_traversal(root)
write (*,*) "Example 1: ", output
! Example 2
root => binary_tree_node(1, &
binary_tree_node(2, &
null(), &
binary_tree_node(4)), &
binary_tree_node(3))
output = binary_tree_preorder_traversal(root)
write (*,*) "Example 2: ", output
end program test_binary_tree_preorder_traversal
temp.f95:6:40:
6 | public :: binary_tree_preorder_traversal
| 1
Error: PUBLIC attribute applied to MODULE binary_tree_preorder_traversal at (1)
temp.f95:16:49:
16 | recursive function binary_tree_preorder_traversal(root) result(output)
| 1
Error: MODULE attribute of ‘binary_tree_preorder_traversal’ conflicts with PROCEDURE attribute at (1)
temp.f95:17:55:
17 | type(binary_tree_node), pointer, intent(in) :: root
| 1
Error: Unexpected data declaration statement in CONTAINS section at (1)
temp.f95:18:43:
18 | character(len=:), allocatable :: output
| 1
Error: Unexpected data declaration statement in CONTAINS section at (1)
temp.f95:20:30:
20 | if (associated(root)) then
| 1
Error: Unexpected block IF statement in CONTAINS section at (1)
temp.f95:21:40:
21 | output = trim(adjustl(str(root%val))) // &
| 1
Error: Symbol ‘root’ at (1) has no IMPLICIT type
temp.f95:24:8:
24 | else
| 1
Error: Unexpected ELSE statement in CONTAINS section at (1)
temp.f95:25:19:
25 | output = ""
| 1
Error: Unexpected assignment statement in CONTAINS section at (1)
temp.f95:26:7:
26 | end if
| 1
Error: Expecting END MODULE statement at (1)
temp.f95:27:3:
27 | end function binary_tree_preorder_traversal
| 1
Error: Expecting END MODULE statement at (1)
temp.f95:32:9:
32 | use binary_tree_preorder_traversal
| 1
Fatal Error: Cannot open module file ‘binary_tree_preorder_traversal.mod’ for reading at (1): No such file or directory
compilation terminated.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
def tree2str(t):
if not t:
return ""
if not t.left and not t.right:
return str(t.val)
if not t.right:
return "{}({})".format(t.val, tree2str(t.left))
return "{}({})({})".format(t.val, tree2str(t.left), tree2str(t.right))
The algorithm performs a modified preorder traversal of the binary tree. During the traversal, when we encounter a non-null node, we add the value of the node followed by left and right sub-trees enclosed in parentheses if they are not null. If the right subtree is null but the left subtree is not, then only the left subtree is added in parentheses. This way, we get a unique string representing the binary tree without any redundant empty parentheses. The algorithm works for each of the languages mentioned in the same way. The traversal is performed using recursion which saves nodes' values in the string representation.
#include <string>
#include <cstdlib>
using namespace std;
class TreeNode {
public:
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
string tree2str(TreeNode* t) {
if (t == nullptr) {
return "";
}
if (t->left == nullptr && t->right == nullptr) {
return to_string(t->val);
}
if (t->right == nullptr) {
return to_string(t->val) + "(" + tree2str(t->left) + ")";
}
return to_string(t->val) + "(" + tree2str(t->left) + ")(" + tree2str(t->right) + ")";
}
The algorithm performs a modified preorder traversal of the binary tree. During the traversal, when we encounter a non-null node, we add the value of the node followed by left and right sub-trees enclosed in parentheses if they are not null. If the right subtree is null but the left subtree is not, then only the left subtree is added in parentheses. This way, we get a unique string representing the binary tree without any redundant empty parentheses. The algorithm works for each of the languages mentioned in the same way. The traversal is performed using recursion which saves nodes' values in the string representation.