加入二叉樹

Question

假設我們有一組二叉樹，其中有序和前序遍歷，並且沒有樹是給定集合中另一棵樹的子樹。現在給出另一個二叉樹Q，找出它是否可以通過加入給定集合中的二叉樹來形成（同時加入集合中的每棵樹應該被認爲是最後一次）加入操作意味着：

選擇集合中的任何樹並將其掛接到另一棵樹的任何頂點，使得生成的樹也是二叉樹。

我們可以使用LCA（最小共同祖先）來做到這一點嗎？還是需要任何特殊的數據結構來解決？

Answer 1

我認爲二叉樹結構應該足夠了。我不認爲你需要任何其他特殊的數據結構。

我不明白你會如何使用生命週期評估。據我所知，LCA用於瞭解同一棵樹中兩個NODES的最低公共祖先。它不會幫助比較兩棵樹。 （這是我會做什麼來檢查是否可以形成Q）

我的解決方案是文字。

樹Q必須檢查，如果它可以從一組樹，所以我會採取自上而下的方法。基本上將Q與由該集合形成的可能的樹相比較。

邏輯： 如果Q.root與集合（A，B，C .... Z ...）中的任何樹根都不匹配，則無法解決問題。

如果Q.root匹配樹根（比如A），檢查相應的子項並將A標記爲used/visited。 （這是我從這個問題中瞭解到的：一棵樹只能使用一次）

只有當所有Q的子元素都與A的相應子元素相匹配時，我們才應該繼續使用A（我會做深度優先遍歷，廣度優先也可以）。

我們可以從集合中追加一棵新的樹（即僅在A的葉節點追加新的根（樹B），就像我們必須維護二叉樹一樣）。跟蹤B的附加位置。

重複與相應的兒童比較相同的檢查，如A所做。如果不匹配，請刪除B並嘗試在添加了B的地方添加C樹。 （除非我們想要IDENTICAL MATCH，在這種情況下，我們會嘗試其他的樹組合，而不是我們擁有的樹組合，它們與Q匹配，但有更多的節點） 。

道歉爲冗長冗長的答案。 （我覺得我的僞代碼很難編寫，並且有很多解釋的評論）。

希望這會有所幫助。

另一種解決方案：效率會低得多（只在樹數相對較少的情況下嘗試）：形成所有可能的樹集合（首先是2s然後3s ... N）並且檢查已形成的樹如果他們是相同的Q. 比較部件可以在這裏簡稱： http://www.geeksforgeeks.org/write-c-code-to-determine-if-two-trees-are-identical/