Временная сложность клонирования двоичного дерева

Question

Мне интересно, имеет ли этот код, который клонирует двоичное дерево, временную сложность O (n)? если это O (n), вы можете объяснить, почему? если нет, можете ли вы предложить способ сделать это с временной сложностью O (n)?

public TreeNode cloneTree(TreeNode root) {
    if (root == null) return null;
    TreeNode newNode = new TreeNode(root.val);
    newNode.left = cloneTree(root.left);
    newNode.right = cloneTree(root.right);
    return newNode;
} 

Answer 1

Вы можете подумать, что это O (2 ⁿ ) из-за двух рекурсивных дочерних вызовов, но все алгоритмы обхода дерева, подобные этому, имеют O (n). Каждый узел дерева посещается только один раз; если вы добавите к дереву 10 узлов, вы получите еще 10 кадров стека, порожденных алгоритмом, что является линейной зависимостью. Да, фрейм имеет предварительные, промежуточные и постэтапные этапы для дочерних посещений, поэтому управление действительно возвращается обратно во фрейм несколько раз, но это нормальное линейное поведение, и нет никакого способа улучшить сложность при посещении каждого узла в дерево.