algorithm - 一起遍历两棵树？

Question

我正在寻找很多面试问题，其中的问题需要同时遍历两棵树，但我不确定具体如何去做。

例如

Given references to roots of two binary trees, how do you determine whether the sequence of the leaf elements equal but you must implement short circuiting return when the first node violates the rule.

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
}