二叉树同构检测递归算法的时间复杂度是否为线性？

我在GeeksforGeeks的「Check if Tree is Isomorphic」挑战中，发现关于同构判断算法的最坏时间复杂度存在多种矛盾说法。

先明确问题定义：

给定两棵二叉树，判断它们是否同构。

说明：
若通过一系列翻转操作（即交换若干节点的左右子节点）可将一棵树转化为另一棵树，则称这两棵树同构。任意层级的任意数量节点均可交换其子节点。两棵空树视为同构。

例如，以下两棵树是同构的，涉及翻转的子树为：2和3、NULL和6、7和8。

针对该问题，有如下递归实现的判断算法：

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

各方时间复杂度说法 #

官方分析观点 #

时间复杂度： O(min(N1, N2))，其中N1和N2分别为两棵树的节点数。算法仅遍历到较小树的节点结束位置，因为若较小树遍历完毕，较大树的额外节点无法在较小树中找到对应节点，此时两棵树不同构。因此算法时间复杂度取决于两棵树中较小的节点数，即min(N1, N2)。

置顶评论文章观点 #

该算法的时间复杂度为O(n)，其中n为树的节点数。因为每个节点仅被访问一次。

部分评论的反对观点（推导为O(N²)） #

假设树有L层，标记为l到0，其中0为最底层。
则T(l) = 4T(l-1)+c（为简化假设4次递归检查耗时相同）
T(l) = 4^L + c(4+4²⁺⁴3+....+4^(l-1))
T(l) = 4^L+c*4L

T(L) = c*4^L

由于L=logN，因此T(L)=c*4^LogN

O(N)=2^(2*LogN)=N²

反对方的反驳逻辑 #

要么调用节点的左右子节点检查，若返回true则不会再次调用该节点的左右子节点；若第一种情况返回false，则不会继续调用所选节点的后续分支，转而调用第二种情况的左右交叉检查。

我个人猜测，或许因为每层仅进行2次比较，总比较次数为2^h，而2log(n)=n。

那么该特定算法的真实时间复杂度究竟是多少？哪方观点正确？

内容的提问来源于stack exchange，提问作者Adrian