證明一棵二叉樹是另一棵的子樹

Question

假設你有兩棵二叉樹，你想知道它是否是另一棵的一棵子樹。一種解決方案是獲取兩棵樹的順序和前序遍歷，並檢查候選子樹的遍歷是否是另一棵樹的相應遍歷的子串。我閱讀了幾篇關於這個解決方案的文章。其中一個discussion顯示順序和前序遍歷都是必需的。有人可以解釋他們爲什麼足夠嗎？爲什麼如果tree2的inorder和preorder遍歷是那些tree1的子串，那麼tree2是tree1的一個子樹？

Answer 1

問：一個討論表明，中序和序遍歷都是 必要的。有人可以解釋他們爲什麼足夠嗎？

由於簡單的事實，所以能夠唯一地重建從這兩個遍歷的二進制樹的（或序和後序，以及）。檢查這個例子：

Inorder : [1,2,3,4,5,6] 
    Preorder : [4,2,1,3,5,6] 

從前序，你知道4是樹的根。從序，你能確定左，右子樹，你從這個角度出發遞歸：

    4 
      / \ 
    Left subtree  Right subtree 
    Inorder : [1,2,3] Inorder : [5,6] 
    Preorder: [2,1,3] Preorder: [5,6] 

檢查這個優秀的文章中更多的細節： Reconstructing binary trees from tree traversal。由於這兩個結合在一起的樹的串行化（實際上將樹序列化爲一個字符串）必須是二叉樹唯一的，所以當且僅當這些遍歷是其他兩個串行化的子串時，我們才能得到這棵樹是另一棵樹的子樹。

Answer 2

人們同意二叉樹可以通過左/右關係表示節點上的順序。這意味着左邊部分在右邊部分之前。如果訂單相同，您可以調用相同的樹木。所以順序串表示順序，如果你想檢查等價性，那麼僅檢查順序（按定義）就足夠了。 但是，當你想檢查樹的完全平等時，我們必須找到如何區分等價樹的方式。例如，它可以是水平順序檢查。但是對於子樹級別的順序不適合，因爲子樹的級別順序字符串被拆分。對於預購，您可以在樹的其他部分之前行走子樹樹根。

假設等價樹不相等，那麼在預先遍歷中，所有東西都是相等的，直到第一個不同。 2種情況可能發生。

1）一棵樹的節點值不同。這意味着預購字符串不同，因爲您按預訂順序走樹。

2）孩子簽名（沒有孩子，只有左邊，只有右邊，兩個孩子）不同。但在這種情況下，易於理解的是有序變化和樹木不等價，這與條件相矛盾。

請注意，這僅適用於所有節點都是唯一的。如果你的所有節點的價值都是「a」，那麼無論你如何走路，你的字符串總是「aa ... a」。所以你必須以某種方式區分節點，而不僅僅是「價值」。