Подсчет совпадающих узлов на дереве

Question

Я пытаюсь решить эту проблему на Practice-It, но у меня возникли проблемы с ней в течение достаточно долгого времени.

Напишите совпадения метода, которые возвращают счетчик количество узлов в одном дереве, которые соответствуют узлам в другом дереве. Совпадение определяется как пара узлов, которые находятся в одном и том же положении в двух деревьях относительно их общего root и в которых хранятся одни и те же данные.

До сих пор я пробовал ниже, но я не совсем понимаю количество, которое я хочу, и я не совсем уверен, почему.

public int matches(IntTree t2)
{
    return match(overallRoot, t2.overallRoot);
}

public int match(IntTreeNode tree1, IntTreeNode tree2)
{
    if(tree1 == null && tree2 == null)
        return 1;
    if(tree1 == null || tree2 == null)
        return 0;
    if(tree1.data == tree2.data)
        return 1;
    int left = match(tree1.left, tree2.left);
    int right = match(tree1.right, tree2.right);
    return left + right; 
}

Любая помощь будет по достоинству оценена!

Answer 1

Вы прекращаете поиск, если текущий узел совпадает. Если все по-другому, вы проверяете влево и вправо, но в матче вы возвращаете один.

Answer 2

Полный ответ для практики это один:

int matches(IntTree tree2) {
    return matches(tree2.overallRoot, this.overallRoot);
}
int matches(IntTreeNode tree1, IntTreeNode node2)
{
    int left=0, right=0, count =0;
    if(tree1 == null && this != null || this == null && tree1 != null) { return 0; }
     count = tree1.data == node2.data ? 1 : 0;
    if(tree1.left != null && node2.left !=null){
     left = matches(tree1.left, node2.left);}
    if(tree1.right != null && node2.right !=null){
     right = matches(tree1.right, node2.right);}
    return count + left + right;
}

Answer 3

Вы очень близки к решению, вы должны учитывать:

• если один из узлов равен null, вы можете прекратить посещение поддеревьев и вернуть 0
• если data для двух корней различны, count равно 0, иначе равно 1, и после того, как вы можете вычислить count для двух поддеревьев, добавляя к count для двух корней.

Ниже мои предложения в виде кода:

public int match(IntTreeNode tree1, IntTreeNode tree2) {
    if(tree1 == null || tree2 == null) { return 0; }
    int count = tree1.data == tree2.data ? 1 : 0;
    int left = match(tree1.left, tree2.left);
    int right = match(tree1.right, tree2.right);
    return count + left + right; 
}