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

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){&nbsp; &nbsp; return false;}最好一棵一棵地遍历两棵树。并继续储存叶子。&nbsp; public static boolean compare()&nbsp; {&nbsp; &nbsp; for(int i = 0; i <array1.length ;i ++)&nbsp; &nbsp; &nbsp;{&nbsp; &nbsp; &nbsp; &nbsp;if(array1[i] != array2[i])&nbsp; &nbsp; &nbsp; &nbsp;{&nbsp; &nbsp; &nbsp; &nbsp; return false;&nbsp; &nbsp; &nbsp; &nbsp;}&nbsp; &nbsp; &nbsp;}&nbsp;&nbsp; &nbsp; return true;&nbsp; }public void isSimilar(Node root, int flag){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if(root==null)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;return;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if(root.left == null && root.right == null)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if(flag==1)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; array1[q] =root.val ;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; q++;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; else&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;array2[r] =root.val ;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; r++;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; isSimilar(root.left,flag);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;isSimilar(root.right,flag);}您必须传递一个标志变量来指向要填充的数组。例如，这里 0 指的是tree1并填充array1，1指的是tree2并填充array2：&nbsp;isSimilar(root1, 0);&nbsp;isSimilar(root2, 1);

Answer 2

您的程序将因测试用例而失败：tree1 :&nbsp; &nbsp;1&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;/&nbsp; \&nbsp; &nbsp; &nbsp; null&nbsp; &nbsp;nulltree2:&nbsp; &nbsp; 2&nbsp; &nbsp; &nbsp; &nbsp; /&nbsp; \&nbsp; &nbsp; &nbsp; &nbsp;1&nbsp; &nbsp; null显然，两棵树都只有一个叶节点1，但是您的代码将会失败，因为您对这两棵树进行了相同的迭代。您应该单独迭代它们并将叶节点存储在数组中。最后检查两个数组是否具有相同的元素，无论顺序如何。tree1 :&nbsp; &nbsp; &nbsp; &nbsp;1&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;/&nbsp; \&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 2&nbsp; &nbsp; 3tree2:&nbsp; &nbsp; 1&nbsp; &nbsp; &nbsp; &nbsp; /&nbsp; \&nbsp; &nbsp; &nbsp; &nbsp;3&nbsp; &nbsp; 2上面两棵树有相同的叶子，我已经更新了函数来正确实现它。public int leafSimilar(TreeNode root, int arr[], int l) {&nbsp; &nbsp; if(root == null)&nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; return l;&nbsp; &nbsp; }&nbsp; &nbsp; if(root.left == null && root.right == null)&nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; arr[l] =root.val ;&nbsp; &nbsp; &nbsp; &nbsp; l+=1;&nbsp; &nbsp; &nbsp; &nbsp; return l;&nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp;&nbsp;&nbsp; &nbsp; l = leafSimilar(root.left, l);&nbsp; &nbsp; l = leafSimilar(root.right, l);&nbsp; &nbsp; return l;}public boolean compareLeaves(int arr1[], int arr2[], int l, int r)&nbsp;{&nbsp; &nbsp; &nbsp;if( l != r ) return false;&nbsp; &nbsp; &nbsp;for(int i = 0; i <l ;i ++)&nbsp; &nbsp; &nbsp;{&nbsp; &nbsp; &nbsp; &nbsp;boolean flag = true;&nbsp; &nbsp; &nbsp; &nbsp; for(int j = 0; j <r ;j ++) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;if(arr1[i] == arr2[j])&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;{&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; flag = false;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; break;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;}&nbsp; &nbsp; &nbsp; &nbsp;}&nbsp; &nbsp; &nbsp; &nbsp;if( flag) return false;&nbsp; &nbsp; }&nbsp; &nbsp; &nbsp;return true;&nbsp;}int l = leafSimilar(root1, arr1, 0);int r = leafSimilar(root2, arr2, 0);compareLeaves(arr1, arr2, l, r);如果树可以有重复的节点，上述函数也会失败。更新比较函数以计算数组 1 中所有节点的频率，然后将其与数组 2 中节点的频率进行匹配。它将处理重复的节点。

Answer 3

如果数组的长度不同但第一个元素一致array1.length，我相信您认为它们相等（返回true）。您可能需要使用q和r来确定元素计数是否相同以及要比较的元素数量。如果两个根都是null，我希望树应该被认为是相等的，但是你返回了false。即使root1 == null，你仍然应该捡起叶子root2，反之亦然。我认为你应该进行中序遍历，即在查看andleafSimilar(root1.left,root2.left)&nbsp;之前调用。这可能并不重要，因为只考虑了叶子，但我发现很难 100% 确定。root1.valroot2.valval我可能错过了什么。使用两个不同的数组来存储所有叶子应该是一个合理的策略。我认为如果单独处理每棵树而不是同时处理两棵树会更容易。