data-structures - 克隆二叉树的时间复杂度

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(2n)，但所有像这样的树遍历算法都是 O(n)。树的每个节点只被访问一次；如果向树中添加 10 个节点，则算法会生成 10 个以上的堆栈帧，这是一种线性关系。是的，该框架具有子访问的前、中和后阶段，因此控制确实多次返回到框架，但这是正常的线性行为，并且在访问每个节点时无法提高复杂性树。