algorithm - BST到双链表算法的复杂性？

我在看CC150中的代码其方法之一如下，它通过检索左子树的尾部来完成此操作。

public static BiNode convert(BiNode root) {
    if (root == null) {
        return null;
    }

    BiNode part1 = convert(root.node1);
    BiNode part2 = convert(root.node2);

    if (part1 != null) {
        concat(getTail(part1), root);
    }

    if (part2 != null) {
        concat(root, part2);
    }

    return part1 == null ? root : part1;
}

public static BiNode getTail(BiNode node) {
    if (node == null) {
        return null;
    }
    while (node.node2 != null) {
        node = node.node2;
    }
    return node;
}

public static void concat(BiNode x, BiNode y) {
    x.node2 = y;
    y.node1 = x;
}

public class BiNode {
    public BiNode node1;
    public BiNode node2;
    public int data;
    public BiNode(int d) {
        data = d;
    }
}

我不理解的是作者在O（n ^ 2）中给出的时间复杂度。我得到的结果是t（n）=2*t（n/2）+o（n/2），o（n/2）被getting tail引用消耗，因为它需要遍历o（n/2）的列表长度。所以根据主定理，它应该是o（nlogn）。我做错什么了吗？谢谢您！

最佳答案

公共静态binode convert（binode root）{//bst everything的最坏情况
if（root==null）{//在左分支（node1）上
返回空值；
}
BiNode part1=convert（root.node1）；//调用n次
binode part2=convert（root.node2）；//开始时的单个调用
如果（第一部分！=空）{
concat（gettail（part1），root）；//o（n）每个递归调用
}//最坏情况是从1到n
//见下文
如果（第2部分！=空）{
concat（根，第2部分）；
}
返回part1==null？根：第1部分；
}
公共静态binode gettail（binode节点）{//o（n）
if（节点==空）{
返回空值；
}
while（node.node2！=空）{
node=node.node2；
}
返回节点；
}
公共静态空隙concat（BiNode x，BiNode y）{//O（1）
x.node2=y；
y.node1=x；
}
样本树：
4个
/
三
/
2个
/
一
如您所见，在最坏的情况下（big-oh不是平均情况），bst将仅使用node1分支来构造。因此，递归必须使用“1+2+”运行getTail（）…+完成转换的问题大小。
即o（n^2）