Leaf-Similar Trees

🏠 ⬅️ ➡️

Consider all the leaves of a binary tree, from left to right order, the values of those leaves form a leaf value sequence.

For example, in the given tree above, the leaf value sequence is (6, 7, 4, 9, 8).

Two binary trees are considered leaf-similar if their leaf value sequence is the same.

Return true if and only if the two given trees with head nodes root1 and root2 are leaf-similar.

Example 1:

Input: root1 = [3,5,1,6,2,9,8,null,null,7,4], root2 = [3,5,1,6,7,4,2,null,null,null,null,null,null,9,8] Output: true

Example 2:

Input: root1 = [1,2,3], root2 = [1,3,2] Output: false

Constraints:

  • The number of nodes in each tree will be in the range [1, 200].
  • Both of the given trees will have values in the range [0, 200].
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    type :: TreeNode
        integer :: val
        type(TreeNode), pointer :: left => null(), right => null()
    end type TreeNode

    type (TreeNode), target :: root1, root2
    logical :: result

    call init_tree(root1)
    call init_tree(root2)

    result = leafSimilar(root1, root2)

    print '(L1)', result

contains

    subroutine init_tree(root)
        type (TreeNode), intent(out) :: root

        allocate(root%left)
        allocate(root%right)
        root%val = 3
        root%left%val = 5
        root%right%val = 1
        root%left%left%val = 6
        root%right%left%val = 2
        root%right%right%val = 9
        root%right%left%left%val = 8
        root%right%left%right%val = 7
        root%right%right%left%val = 4
    end subroutine init_tree

end program main

logical function leafSimilar(root1, root2) result(isLeafSimilar)
    type (TreeNode), intent(in) :: root1, root2
    type (TreeNode), pointer :: curr1, curr2
    integer :: leafValueSequence(100)
    integer :: i, j

    ! Initialize the leaf value sequence array
    do i = 1, size(leafValueSequence)
        leafValueSequence(i) = -1
    end do

    ! Traverse both trees simultaneously and fill the leaf value sequence array
    curr1 => root1
    curr2 => root2
    i = 1
    do while (associated(curr1))
        if (.not. associated(curr1%left)) then
            leafValueSequence(i) = curr1%val
            i = i + 1
        end if
        curr1 => curr1%left
        if (.not. associated(curr2)) exit
        curr2 => curr2%left
    end do

    ! Check if the leaf value sequences are equal
    do i = 1, size(leafValueSequence)
        if (leafValueSequence(i) /= curr2%val) return
        curr2 => curr2%left
    end do

    isLeafSimilar = .true.

end function leafSimilar
❌ Compiled
❌ Executed
❌ Correct 
module leaf_similar_trees

implicit none

contains

function is_leaf_similar(root1, root2) result(is_similar)

! This function checks if two binary trees with head nodes root1 and root2 are leaf-similar.

type(node), pointer, intent(in) :: root1, root2
logical :: is_similar

! Create a queue to store the nodes of the two trees
type(node), pointer :: queue1(:), queue2(:)
integer :: front1, back1, front2, back2

! Initialize the queues and the front and back indices
allocate(queue1(200), queue2(200))
front1 = 1
back1 = 0
front2 = 1
back2 = 0

! Add the first nodes of the two trees to the queues
if (associated(root1)) then
    queue1(back1+1) => root1
    back1 = back1 + 1
end if
if (associated(root2)) then
    queue2(back2+1) => root2
    back2 = back2 + 1
end if

! Loop until both queues are empty
do while (front1 <= back1 .or. front2 <= back2)

    ! Get the front nodes of the two trees
    if (front1 <= back1) then
        if (associated(queue1(front1)%left)) then
            queue1(back1+1) => queue1(front1)%left
            back1 = back1 + 1
        end if
        if (associated(queue1(front1)%right)) then
            queue1(back1+1) => queue1(front1)%right
            back1 = back1 + 1
        end if
        front1 = front1 + 1
    end if
    if (front2 <= back2) then
        if (associated(queue2(front2)%left)) then
            queue2(back2+1) => queue2(front2)%left
            back2 = back2 + 1
        end if
        if (associated(queue2(front2)%right)) then
            queue2(back2+1) => queue2(front2)%right
            back2 = back2 + 1
        end if
        front2 = front2 + 1
    end if

    ! If the front nodes are not leaf nodes, add their children to the queues
    if (associated(queue1(front1)%left) .or. associated(queue1(front1)%right)) then
        if (associated(queue1(front1)%left)) then
            queue1(back1+1) => queue1(front1)%left
            back1 = back1 + 1
        end if
        if (associated(queue1(front1)%right)) then
            queue1(back1+1) => queue1(front1)%right
            back1 = back1 + 1
        end if
    end if
    if (associated(queue2(front2)%left) .or. associated(queue2(front2)%right)) then
        if (associated(queue2(front2)%left)) then
            queue2(back2+1) => queue2(front2)%left
            back2 = back2 + 1
        end if
        if (associated(queue2(front2)%right)) then
            queue2(back2+1) => queue2(front2)%right
            back2 = back2 + 1
        end if
    end if

    ! If the front nodes are leaf nodes, check if their values are the same
    if (associated(queue1(front1)%left) .and. associated(queue1(front1)%right)) then
        if (queue1(front1)%val /= queue2(front2)%val) then
            is_similar = .false.
            return
        end if
        front1 = front1 + 1
        front2 = front2 + 1
    end if

end do

! If we reach this point, the two trees are leaf-similar
is_similar = .true.

end function is_leaf_similar

type node
    integer :: val
    type(node), pointer :: left, right
end type
🌐 Data from online sources 
def splitIntoFibonacci(num):
    ans = []
    def backtrack(index, prev1, prev2):
        if index == len(num):
            return len(ans) >= 3
        curr = 0
        for i in range(index, len(num)):
            if i > index and num[index] == '0':
                break
            curr = curr * 10 + ord(num[i]) - ord('0')
            if curr > 2**31 - 1:
                break
            if len(ans) >= 2:
                if curr < prev1 + prev2:
                    continue
                elif curr > prev1 + prev2:
                    break
            ans.append(curr)
            if backtrack(i + 1, prev2, curr):
                return True
            ans.pop()
        return False

    backtrack(0, 0, 0)
    return ans

The algorithm uses backtracking to solve the problem. It starts by iterating through the input string, parsing every possible length substring as numbers. The algorithm maintains a list, 'ans', to keep track of the Fibonacci-like sequence formed so far and also stores the previous 2 numbers in the sequence.

The base case is when the entire string has been processed (i.e., index == string length) and the 'ans' list has at least 3 elements. In that case, we return true and stop further processing.

While iterating through the string and parsing substrings, we perform the following steps: 1. Skip the current substring if it has a leading zero but isn't just "0". 2. If the current number is greater than the 32-bit integer limit, break because it can't be a valid Fibonacci number. 3. If the list 'ans' has at least 2 elements, we check whether the sum of the previous 2 numbers is equal to the current number. If the sum is smaller, we continue to the next substring, whereas if the sum is larger, we break because any larger substring will lead to an invalid sequence. 4. If the current number is a valid candidate, we add it to the 'ans' list. 5. Perform backtracking on the next index with the updated values of previous numbers. If the backtracking returns true, exit early; otherwise, we remove the current number from the 'ans' list and continue with the next substring.

🌐 Data from online sources 
#include <vector>
#include <string>

std::vector<int> splitIntoFibonacci(std::string num) {
    std::vector<int> ans;
    backtrack(num, ans, 0, 0, 0);
    return ans;
}

bool backtrack(std::string& num, std::vector<int>& ans, int index, int prev1, int prev2) {
    if (index == num.size()) {
        return ans.size() >= 3;
    }
    long curr = 0;
    for (int i = index; i < num.size(); ++i) {
        if (i > index && num[index] == '0') {
            break;
        }
        curr = curr * 10 + num[i] - '0';
        if (curr > INT32_MAX) {
            break;
        }

        if (ans.size() >= 2) {
            long sum = (long)prev1 + prev2;
            if (curr < sum) {
                continue;
            } else if (curr > sum) {
                break;
            }
        }

        ans.push_back(curr);
        if (backtrack(num, ans, i + 1, prev2, curr)) {
            return true;
        }
        ans.pop_back();
    }
    return false;
}

The algorithm uses backtracking to solve the problem. It starts by iterating through the input string, parsing every possible length substring as numbers. The algorithm maintains a list, 'ans', to keep track of the Fibonacci-like sequence formed so far and also stores the previous 2 numbers in the sequence.

The base case is when the entire string has been processed (i.e., index == string length) and the 'ans' list has at least 3 elements. In that case, we return true and stop further processing.

While iterating through the string and parsing substrings, we perform the following steps: 1. Skip the current substring if it has a leading zero but isn't just "0". 2. If the current number is greater than the 32-bit integer limit, break because it can't be a valid Fibonacci number. 3. If the list 'ans' has at least 2 elements, we check whether the sum of the previous 2 numbers is equal to the current number. If the sum is smaller, we continue to the next substring, whereas if the sum is larger, we break because any larger substring will lead to an invalid sequence. 4. If the current number is a valid candidate, we add it to the 'ans' list. 5. Perform backtracking on the next index with the updated values of previous numbers. If the backtracking returns true, exit early; otherwise, we remove the current number from the 'ans' list and continue with the next substring.