穿越兩棵樹在一起？

Question

我看到很多面試問題，其中的問題需要遍歷兩棵樹在一起，我不確定如何去做這件事。

例如到的兩個二進制樹樹根

鑑於引用，你如何確定是否 葉元素的順序相同，但是當第一個節點違反 規則必須 實現短路回報。

Answer 1

是您的問題，問以找出是否： 「訪問的兩棵樹的所有葉子節點產生的順序是一樣的」

與約束，當發現葉值不匹配，那麼我們必須立即退出。

如果是的話，我建議以下解決方案：

insert (root of tree1) in stack1 
insert (root of tree2) in stack2 

temp1 = (root of tree1) -> left child 
temp2 = (root of tree2) -> left child 

while(stack1 and stack2 arent empty) 
{ 
    found = false 
    while(found == false) { 
     if (temp1 is leaf node) 
      child1 = value of temp1 
      found = true 
      pop element from stack1 
      set temp1 to its right child 

     if (temp1 has left child) 
      put temp1 in stack1 
      set temp1 to its left child 
    } 

    found = false 
    while(found == false) { 
     if (temp2 is leaf node) 
      child2 = value of temp2 
      found = true 
      pop element from stack2 
      set temp2 to its right child 

     if (temp2 has left child) 
      put temp2 in stack2 
      set temp2 to its left child 
    } 

    if(child1 != child2) 
     return 
} 

Answer 2

在僞代碼：

1. 下到第一葉（假設最左邊的）在每個樹。
2. 比較。
3. 如果不等於RETURN錯誤。
4. 步驟到每棵樹的下一片葉子（直觀地說 - 直到你看到一條路才能步入正確的孩子，然後只帶走左邊的孩子直到你到達樹葉）。
5. 如果其中一棵樹有一片樹葉，但另一棵樹返回到根返回錯誤。
6. 如果兩個樹都返回到根返回成功。
7. 轉到步驟2。

Answer 3

一種可能的解決方案：

• 我已經創建了一個樹類，其具有方法GetNextLeafNode（）。這是負責返回樹的下一個立即葉節點。

• 隨着樹類我保持的堆疊維持橫穿元件

• 在GetNextLeafNode（）方法，我做迭代樹遍歷（預順序）。

每當我遇到一個節點（stack.Pop（）），這是葉，我只是回到它。否則，我會將左指針和右指針推向堆棧。最初推送根節點。在任何時候堆棧狀態都是正確的。

下面是C＃代碼：

public TreeNode GetNextLeafNode() 
    { 
     TreeNode leaf = null; 

     while (s.Count != 0) 
     { 
      TreeNode n = s.Pop(); 
      if ((n.Left == null) && (n.Right == null)) 
      { 
       leaf = n; 
       return leaf; 
      } 
      else 
      { 
       if (n.Right != null) 
        s.Push(n.Right); 
       if (n.Left != null) 
        s.Push(n.Left); 
      } 
     } 

     return leaf; 
    } 

現在，我們可以創建兩個不同的樹說，T1和T2。 我們可以做的比較如下：

 int data1 = t1.GetNextLeafNode().Data; 
     int data2 = t2.GetNextLeafNode().Data; 

     while (data1 == data2) 
     { 
      //both the leaf nodes are same. 
      data1 = t1.GetNextLeafNode().Data; 
      data2 = t2.GetNextLeafNode().Data; 
     }