Задача из LeetCode 872. Leaf-Similar Trees | 40 / 42 testcases passed

Question

Задача из LeetCode 872. Leaf-Similar Trees | 40 / 42 testcases passed

Аркадий Саакян Ученик (162), на голосовании 1 год назад

https://leetcode.com/problems/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). Return true if and only if the two given trees with head nodes root1 and root2 are leaf-similar.

Мой код проходит все тесты кроме двух последних.

 class Solution { 
 
    public String backtrack(TreeNode curr) { 
        if (curr.left == null && curr.right == null) 
            return Integer.toString(curr.val); 
        if (curr.left != null && curr.right == null) 
            return backtrack(curr.left); 
        if (curr.left == null && curr.right != null) 
            return backtrack(curr.right); 
        return backtrack(curr.left) + backtrack(curr.right); 
    } 
 
    public boolean leafSimilar(TreeNode root1, TreeNode root2) { 
        return backtrack(root1).equals(backtrack(root2)); 
    } 
}

Answer 1

 class Solution { 
    public boolean leafSimilar(TreeNode root1, TreeNode root2) { 
        List leafSequence1 = new ArrayList<>(); 
        List leafSequence2 = new ArrayList<>(); 
        getLeafSequence(root1, leafSequence1); 
        getLeafSequence(root2, leafSequence2); 
        return leafSequence1.equals(leafSequence2); 
    } 
 
    private void getLeafSequence(TreeNode node, List leafSequence) { 
        if (node == null) return; 
        if (node.left == null && node.right == null) { 
            leafSequence.add(node.val); 
        } else { 
            getLeafSequence(node.left, leafSequence); 
            getLeafSequence(node.right, leafSequence); 
        } 
    } 
}

Answer 2

Давайте сначала посмотрим на изображение, которое вы загрузили, чтобы лучше понять проблему.

Спасибо за изображение. Ваш подход к решению задачи состоит в том, чтобы представить последовательность листьев дерева в виде строки, а затем сравнить эти строки для обоих деревьев.

Однако ваш метод `backtrack` может не работать корректно в некоторых случаях. В частности, если у вас есть два листа с значениями 12 и 3, ваш метод вернет строку "123", что также может быть получено из двух листьев с значениями 1 и 23. Это может вызвать неверное сравнение.

Чтобы решить эту проблему, вы можете использовать разделитель между значениями листьев при формировании строки. Например, вы можете использовать символ "-", чтобы ваша строка выглядела как "12-3" вместо "123".

Давайте внесем это изменение в ваш код и проверим его работу.

Вот обновленный код:

```java
class Solution {

public String backtrack(TreeNode curr) {
if (curr.left == null && curr.right == null)
return Integer.toString(curr.val) + "-";
if (curr.left != null && curr.right == null)
return backtrack(curr.left);
if (curr.left == null && curr.right != null)
return backtrack(curr.right);
return backtrack(curr.left) + backtrack(curr.right);
}

public boolean leafSimilar(TreeNode root1, TreeNode root2) {
return backtrack(root1).equals(backtrack(root2));
}
}
```

Попробуйте выполнить этот код на тестовых примерах, которые не проходили ранее, чтобы проверить его работоспособность.