克隆二进制树的时间复杂度

Question

我想知道如果这个代码，克隆二进制树是在时间复杂度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个算法催生的堆栈框架，这是一种线性关系。是的，框架对子代的访问有前、中、后三个阶段，所以控制确实会多次返回框架，但这是正常的线性行为，没有办法在访问树上每个节点的同时提高复杂度。