克隆二叉树的时间复杂度 [英] Time complexity of cloning a binary tree

问题描述

我想知道克隆二进制树的代码是否在时间复杂度O(n)中? 如果它的O(n)可以解释原因? 如果不是，您可以建议一种方法来解决时间复杂度O(n)吗?

i am wondering if this code that clones binary tree is in time complexity O(n)? if its O(n) can you explain why? if not, can you suggest a way to do it in time complexity 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;
} 

推荐答案

由于两个递归子调用，您可能会认为它是O(2 ⁿ )，但是所有像这样的树遍历算法都是O (n).树的每个节点仅被访问一次；如果将10个节点添加到树中，则算法还会产生10个堆栈帧，这是线性关系.是的，框架具有子访问的前，中和后阶段，因此控制确实会多次返回框架，但这是正常的线性行为，在访问节点中的每个节点时，无法提高复杂性树.

You might think it's O(2ⁿ) because of the two recursive child calls, but all tree walking algorithms like this are O(n). Every node of the tree is visited only one time; if you add 10 nodes to the tree, you get 10 more stack frames spawned by the algorithm, which is a linear relationship. Yes, the frame has pre-, in- and post- stages to the child visits, so control does return back to the frame multiple times, but this is normal linear behavior and there's no way to improve the complexity while visiting each node in the tree.

这篇关于克隆二叉树的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！