找出两棵树是否有相似的叶子（从左到右）？

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叶子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 指的是tree1并填充array1，1指的是tree2并填充array2：

 isSimilar(root1, 0);

 isSimilar(root2, 1);

Answer 2

您的程序将因测试用例而失败：

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);

如果树可以有重复的节点，上述函数也会失败。更新比较函数以计算数组 1 中所有节点的频率，然后将其与数组 2 中节点的频率进行匹配。它将处理重复的节点。

Answer 3

1. 如果数组的长度不同但第一个元素一致array1.length，我相信您认为它们相等（返回true）。您可能需要使用q和r来确定元素计数是否相同以及要比较的元素数量。

2. 如果两个根都是null，我希望树应该被认为是相等的，但是你返回了false。

3. 即使root1 == null，你仍然应该捡起叶子root2，反之亦然。

4. 我认为你应该进行中序遍历，即在查看andleafSimilar(root1.left,root2.left) 之前调用。这可能并不重要，因为只考虑了叶子，但我发现很难 100% 确定。root1.valroot2.valval

我可能错过了什么。

使用两个不同的数组来存储所有叶子应该是一个合理的策略。我认为如果单独处理每棵树而不是同时处理两棵树会更容易。