穿越两棵树在一起？

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