Найти, если 2 дерева имеют похожие листья (слева направо)?

Question

Что касается моей логики, я использую два разных массива для хранения всех листьев, а затем сравниваю эти массивы, чтобы увидеть, действительно ли листья одинаковы, но мои тестовые примеры дают сбой (например, [3,5, 1,6,2,9,8, ноль, ноль, 7,4] [3,5,1,6,7,4,2, ноль, ноль, ноль, ноль, ноль, ноль, 9,8]). Заранее спасибо!

'' 'Решение класса {

static int array1[] = new int[50];
static int array2[] = new int[50];
static int q = 0;
static int r = 0;

 public boolean compareLeaves(int arr1[], int arr2[])
 {
     for(int i = 0; i <array1.length ;i ++)
    {
        if(array1[i] != array2[i])
        {
            return false;
        }
    }
     return true;
 }
public boolean leafSimilar(TreeNode root1, TreeNode root2) {

    if(root1 == null || root2 == null)
    {
        return false;
    }

    if(root1.left == null && root1.right == null)
    {
        array1[q] =root1.val ;
        q++;
    }

    if(root2.left == null && root2.right == null)
    {
        array2[r] =root2.val ;
        r++;
    }
    leafSimilar(root1.left,root2.left);
    leafSimilar(root1.right,root2.right);

  return compareLeaves(array1,array2);


}

}' ''

Answer 1

ваша программа потерпит неудачу для контрольного примера:

tree1 :   1
         /  \
      null   null

tree2:    2
        /  \
       1    null

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

tree1 :       1
             /  \
            2    3

tree2:    1
        /  \
       3    2

Над двумя деревьями одинаковые листья, я обновил функции, чтобы реализовать их правильно.

public int leafSimilar(TreeNode root, int arr[], int l) {

    if(root == null)
    {
        return l;
    }

    if(root.left == null && root.right == null)
    {
        arr[l] =root.val ;
        l+=1;
        return l;
    }        
    l = leafSimilar(root.left, l);
    l = leafSimilar(root.right, l);
    return l;
}

public boolean compareLeaves(int arr1[], int arr2[], int l, int r)
 {
     if( l != r ) return false;

     for(int i = 0; i <l ;i ++)
     {
       boolean flag = true;
        for(int j = 0; j <r ;j ++) {
         if(arr1[i] == arr2[j])
         {
            flag = false;
            break;
         }
       }
       if( flag) return false;
    }
     return true;
 }

int l = leafSimilar(root1, arr1, 0);
int r = leafSimilar(root2, arr2, 0);
compareLeaves(arr1, arr2, l, r);

Также вышеприведенная функция потерпит неудачу, если дерево может иметь дублирующий узелОбновите функцию сравнения, чтобы подсчитать частоту всех узлов в первом массиве, а затем сопоставить ее с частотой узлов в массиве 2. Он будет обрабатывать дубликаты узлов.

Answer 2

В следующей строке кода предлагается, чтобы оба дерева следовали по одному и тому же пути, игнорируя при этом листья в одном из tree1 или tree2.

if(root1 == null || root2 == null)
{
    return false;
}

Лучше пройти обадерево по одному. И продолжайте хранить листья.

  public static boolean compare()
  {
    for(int i = 0; i <array1.length ;i ++)
     {
       if(array1[i] != array2[i])
       {
        return false;
       }
     } 
    return true;
  }

public void isSimilar(Node root, int flag)
{

            if(root==null)
             return;
            if(root.left == null && root.right == null)
            {
                if(flag==1)
                {
                    array1[q] =root.val ;
                    q++;
                }
                else
                {
                   array2[r] =root.val ;
                    r++; 
                }
            }

            isSimilar(root.left,flag);
             isSimilar(root.right,flag);

}

Вы должны передать переменную флага, чтобы указать, какой массив заполнить. Например, здесь 0 относится к дереву 1 и заполнению массива 1, а 1 относится к дереву 2 и заполнению массива 2:

 isSimilar(root1, 0);
 isSimilar(root2, 1);

Answer 3

1. Если массивы имеют разную длину, но согласны с первыми array1.length элементами, я полагаю, что вы считаете их равными (возврат true). Вам, вероятно, нужно использовать q и r для определения того, является ли количество элементов одинаковым и сколько элементов сравнивать.
2. Если оба корня равны null, я ожидаю, что деревья должны бытьсчитается равным, но вы возвращаете false.
3. Даже если root1 == null, вы все равно должны забрать листья с root2 и наоборот.
4. Я думаю, что вы должны сделать в порядке обхода, то есть звоните leafSimilar(root1.left,root2.left) до , смотрите на root1.val и root2.val. Возможно, это не имеет значения, поскольку val рассматривается только для листьев, но мне трудно быть на 100% уверенным.

Возможно, я что-то пропустил.

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