一起遍历两棵树？

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
}