Проезжая два дерева вместе?

Question

Я ищу много проблем с собеседованием, когда вопрос требует пересечения двух деревьев вместе, я точно не знаю, как это сделать.

например.

Учитывая ссылку на корни двух бинарных дерев, как вы определяете, ли последовательность листовых элементов равны, но вы должны осуществить короткое возвращение замыканий, когда первый узел нарушает правила .

Answer 1

Ваш вопрос с просьбой выяснить: «последовательность создана, посетив все узлы листьев 2 деревьев же»

с ограничением, что при обнаружении несоответствия значений листа, то мы должен немедленно уйти.

Если да, то я предлагаю следующее решение:

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. Если у одного из деревьев есть лист, а другой возвращается к ошибке RETURN root.
6. Если оба дерева возвращены в корень RETURN success.
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. Мы можем сделать Comparision следующим образом:

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