N元樹 - 它是否對稱

Question

給定一個N元樹，找出它是否對稱於通過樹的根節點繪製的線。在二叉樹的情況下很容易做到這一點。然而，對於N-ary樹，它似乎很難

Answer 1

這並不困難。我打算用這個問題打高爾夫球。我得到7 ...任何人都變好了？思考這個問題

data Tree = Tree [Tree] 
symmetrical (Tree ts) = 
    (even n || symmetrical (ts !! m)) && 
    all mirror (zip (take m ts) (reverse $ drop (n - m) ts)) 
    where { n = length ts; m = n `div` 2 } 
mirror (Tree xs, Tree ys) = 
    length xs == length ys && all mirror (zip xs (reverse ys)) 

Answer 2

一種方法是發現樹是對稱的，如果它是它自己的倒影，其中一棵樹的反射是遞歸定義：

1. 空的反射樹本身。
2. 具有根r和子c1，c2，...，cn的樹的反射是具有根r並且子反射（cn），...，reflect（c2），reflect（c1）的樹。

然後，您可以通過計算樹的反射並檢查它是否等於原始樹來解決此問題。這又可以遞歸地完成：

1. 空的樹只等於它自己。
2. 具有根r和子元素c1，c2，...，cn的樹等於另一棵樹T，如果另一棵樹非空，具有根r，具有n個子元素，並且子元素等於c1，...。 ..，cn按此順序。

當然，這樣做效率有點低，因爲它在進行比較之前完全複製了樹。內存使用量爲O（n + d），其中n是樹中保存副本的節點數量，d是樹的高度（在遞歸tom檢查中是否保持相等）。由於d = O（n），所以使用O（n）存儲器。然而，它運行在O（n）時間，因爲每個階段只訪問一次節點。

這樣做是使用下面的遞歸形式的更節省空間的方法：

1. The empty tree is symmetric. 
2. A tree with n children is symmetric if the first and last children are mirrors, the second and penultimate children are mirrors, etc. 

然後，您可以定義兩棵樹是鏡子如下：

1. 空樹只是其本身的一面鏡子。
2. 具有根r和子c1，c2，...，cn的樹是具有根t和子d1，d2，...，dn的樹的鏡像iff r = t，c1是dn的鏡像，c2是dn-1的鏡像等等。

這種方法也運行在線性時間，但是並不構成樹的完整副本。因此，內存使用量只有O（d），其中d是樹的深度。這是最壞的O（n），但很可能要好得多。

Answer 3

堆棧 現在每次開始遍歷根節點時， 現在遞歸地調用一個函數，並在特定級別上逐個推送左子樹的元素。 維護一個全局變量並在每次將一個左子樹推入堆棧時更新它的值。現在遞歸地調用（在遞歸調用左子樹之後）右子並彈出每個正確匹配。這將確保它是以對稱方式進行檢查。

最後，如果堆棧爲空，所有的元素都被處理了，堆棧的每個元素都被彈出來了......你已經完成了！

Answer 4

我只是在左邊的子樹上按順序遍歷樹（節點向左）並將它保存到列表中。然後在右邊的子樹上再次按順序遍歷樹（node right left）並將其保存到列表中。然後，你可以比較兩個列表。他們應該是一樣的。