二叉树同构的递归方法实际上是线性的吗？

Question

采用以下算法来查找两个二叉树是否同构。

isomorphic(Node root1, Node root2) {
    if (root1 == null && root2 == null) {
        return true;
    }
    if (root1 == null || root2 == null) {
        return false;
    }
    if (root1.data != root2.data) {
        return false;
    }
    return (isIsomorphic(root1.left, root2.left) &&
            isIsomorphic(root1.right, root2.right)) ||
           (isIsomorphic(root1.left, root2.right) &&
            isIsomorphic(root1.right, root2.left));
}

来源：geeksforgeeks

他们声称这段代码的时间复杂度是 O(n)，因为我们访问每个节点一次。正如评论者指出的那样，这不是真的。

Answer 1

您给出的代码需要 O(n²) 时间。

确定有根树的同构问题，其中子级的顺序无关紧要，可以在线性时间内很容易完成。

为此，您可以递归地为两个树中的每个节点分配一个整数，这样两个节点将具有相同的编号（当且仅当它们是同构时）。 要获取节点的编号：

1. 递归获取每个 then 节点的子节点的数字，并将它们放入列表中；
2. 对列表中的数字进行排序，因为子级的顺序无关紧要；
3. 将节点的数据添加到列表中；和
4. 获取列表的编号。 为此，您需要保留从您见过的列表到其号码的映射。 如果列表在地图中，则获取关联的号码。 否则创建一个新号码并将列表->号码映射添加到地图中。
5. 节点的编号就是其列表的编号。

使用此过程，只需获取要比较的两棵树的根的数字即可。 它们是同构的，当且仅当它们具有相同的数字。