一起遍历两棵树？

Question

我看到很多面试问题需要同时遍历两棵树，但我不确定该如何做。

例如：

给定两棵二叉树的根节点引用，如何确定叶子元素的序列是否相等，但必须在第一个节点违反规则时实现短路返回。

- Usman Ismail

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
}

- Tejas Patil

---

如果temp1不是叶节点，且只有一个右（叶）子节点，你该如何到达那里？ - Subhransu Mishra

Answer 2

一种可能的解决方案：

• 我创建了一个树类，其中有一个方法 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;
        }

- Algorist

Answer 3

伪代码：

1. 从每棵树的最左侧的叶子节点开始向下。
2. 比较两个叶子节点。
3. 如果不相等，则返回错误。
4. 移动到每棵树的下一个叶子节点（直观地说，向上走，直到看到一条通向右子节点的路径，然后在到达叶子节点之前只选择左子节点）。
5. 如果其中一棵树有一个叶子节点，但另一棵树已经返回到根节点，则返回错误。
6. 如果两棵树都返回到根节点，则返回成功。
7. 转到第2步。

- Massimiliano

---

你提出的解决方案听起来不错，第四步似乎可以通过中序遍历来完成。 - Anupam Saini

Answer 4

一个简单的Python解决方案。 虽然这不是空间最优的，因为我们存储了可能是O(N+M)的叶子节点。但是这不会同时迭代两棵树。 时间复杂度 - O(N+M)。

您也可以考虑一种空间为O(max(N,M))的类似解决方案。

def binaryTreeLeafs(root1, root2):

    # The order in which we see leaves will
    # be maintained as it is inorder traversal.
    def dfs(node, leaves):
        if not node:
            return
        if not node.left and not node.right:
            leaves.append(node.val)
            return
        dfs(node.left, leaves)
        dfs(node.right, leaves)

    leaves1 = []
    leaves2 = []
    dfs(root1, leaves1)
    dfs(root2, leaves2)
    return leaves1 == leaves2


# O(h1+h2) space
def binaryTreeLeaves2(root1, root2):
    def isLeaf(node):
        return not node or node.left == node.right == None
    if not root1 and not root2:
        return True
    if (not root1) ^ (not root2):
        return False
    stack1 = [root1]
    stack2 = [root2]
    while stack1 or stack2:
        if (not stack1) ^ (not stack2):
            return False
        tmp1 = stack1.pop()
        while not isLeaf(tmp1):
            if tmp1.right:
                stack1.append(tmp1.right)
            if tmp1.left:
                stack1.append(tmp1.left)
            tmp1 = stack1.pop()
        tmp2 = stack2.pop()
        while not isLeaf(tmp2):
            if tmp2.right:
                stack2.append(tmp2.right)
            if tmp2.left:
                stack2.append(tmp2.left)
            tmp2 = stack2.pop()
        if ((not tmp1) ^ (not tmp2)) or (tmp1 and tmp2 and tmp1.val != tmp2.val):
            return False        
    return True 

- Ultrablendz