首頁猿問找出兩棵樹是否有相似的葉子（從左到右）？

找出兩棵樹是否有相似的葉子（從左到右）？

Java

HUH函數(shù) 2023-09-27 14:53:17

就我的邏輯而言，我使用兩個不同的數(shù)組來存儲所有葉子，然后比較這些數(shù)組以查看葉子是否確實相同，但我的測試用例失敗了（例如[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);}} '''

查看完整描述

3 回答

撒科打諢

TA貢獻1934條經(jīng)驗獲得超2個贊

下面的代碼行建議兩棵樹遵循相同的路徑，從而忽略或之一中的tree1葉子tree2。

if(root1 == null || root2 == null)

{

return false;

}

最好一棵一棵地遍歷兩棵樹。并繼續(xù)儲存葉子。

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

}

您必須傳遞一個標志變量來指向要填充的數(shù)組。例如，這里 0 指的是tree1并填充array1，1指的是tree2并填充array2：

isSimilar(root1, 0);

isSimilar(root2, 1);

反對回復 2023-09-27

牧羊人nacy

TA貢獻1862條經(jīng)驗獲得超7個贊

您的程序?qū)⒁驕y試用例而失敗：

tree1 : 1

/ \

null null

tree2: 2

/ \

1 null

顯然，兩棵樹都只有一個葉節(jié)點1，但是您的代碼將會失敗，因為您對這兩棵樹進行了相同的迭代。您應該單獨迭代它們并將葉節(jié)點存儲在數(shù)組中。最后檢查兩個數(shù)組是否具有相同的元素，無論順序如何。

tree1 : 1

/ \

2 3

tree2: 1

/ \

3 2

上面兩棵樹有相同的葉子，我已經(jīng)更新了函數(shù)來正確實現(xiàn)它。

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

如果樹可以有重復的節(jié)點，上述函數(shù)也會失敗。更新比較函數(shù)以計算數(shù)組 1 中所有節(jié)點的頻率，然后將其與數(shù)組 2 中節(jié)點的頻率進行匹配。它將處理重復的節(jié)點。

反對回復 2023-09-27

精慕HU

TA貢獻1845條經(jīng)驗獲得超8個贊

如果數(shù)組的長度不同但第一個元素一致array1.length，我相信您認為它們相等（返回true）。您可能需要使用q和r來確定元素計數(shù)是否相同以及要比較的元素數(shù)量。
如果兩個根都是null，我希望樹應該被認為是相等的，但是你返回了false。
即使root1 == null，你仍然應該撿起葉子root2，反之亦然。
我認為你應該進行中序遍歷，即在查看andleafSimilar(root1.left,root2.left) 之前調(diào)用。這可能并不重要，因為只考慮了葉子，但我發(fā)現(xiàn)很難 100% 確定。root1.valroot2.valval